백준 5430번 AC: C언어, Python 풀이

백준 5430 AC 문제의 C언어, 파이썬 풀이입니다.
덱을 이용한 풀이로, 배열의 뒤집힘 상태와 입출력 방안에 대한 설명을 담고 있습니다.

Python만 보기

전략

상태 변환 방법

배열이 뒤집혀 있으면 뒤에서 빼고, 뒤집혀 있지 않으면 앞에서 빼면 된다.
양쪽에서 삭제가 가능해야 하니 덱을 사용하면 된다.

상태는 뒤집혀진 상태를 1 일반 상태를 0으로 둔다.
XOR 연산을 통해 상태 전환, 토글이 가능하다.

if (functions_buffer[i] == REVERSE)
{
    // Switch state
    state = state ^ 1;
}
// Delete
else 
{
    // Reversed: 1, Normal: 0 
    head += state ^ 1;
    tail -= state;
} 

입력 받기

입출력이 생각보다 까다로웠다.
쉼표에 괄호도 붙어있고 빈 배열이라는 특수 케이스도 존재한다.

처음 고안한 방식은 다음과 같다.

void fill_dequeue(int *dequeue, int dequeue_size)
{
    char c;
    while ((c = getchar()) != '[');
    for (int i = 0; i < dequeue_size; i++)
    {
        scanf("%d", &dequeue[i]);
        // Consume comma
        getchar();
    }
    while ((c = getchar()) != '\n');
}

이렇게 해도 정답은 맞지만
속도를 빠르게 해보기 위해 아래를 시도해보았다.

// Parse input buffer, store it as int 
int curr = 0;
int tmp = 0; 
for (int i = 1; input_buffer[i] != '\0'; i++)
{
    if (input_buffer[i] == ',' || input_buffer[i] == ']')
    {
        output_array[curr++] = tmp;

        // Initialize tmp
        tmp = 0;
    }
    // buf[i] is a digit
    else
    {
        tmp = tmp * 10 + input_buffer[i] - '0';
    }
}

전체 배열 입력을 한번에 받고, 임시 변수에 숫자를 저장, 자릿수가 오를 때마다 10을 곱한다.
,나 ]와 같은 문자가 나오면 임시 변수를 저장, 임시 변수를 초기화 해주면 된다.

C 코드

#include <stdio.h>

#define MAX_ARRAY_SIZE 100001
#define MAX_FUNCTION_SIZE 100001
#define MAX_INPUT_BUFFER_SIZE 400001

enum function
{
    REVERSE = 'R',
    DELETE = 'D'
};

enum dequeue_state
{
    REVERSED = 1,
    NORMAL = 0,
};

int main(void)
{
    int num_cases;
    scanf("%d\n", &num_cases);

    char functions_buffer[MAX_FUNCTION_SIZE];
    char input_buffer[MAX_INPUT_BUFFER_SIZE];
    int output_array[MAX_ARRAY_SIZE];

    int array_size;
    for (int i = 0; i < num_cases; i++)
    {
        scanf("%s\n", functions_buffer); 
        scanf("%d\n", &array_size);
        scanf("%s\n", input_buffer);

        enum dequeue_state state = NORMAL;
        int head = 0;
        int tail = array_size;
        for (int i = 0; functions_buffer[i] != '\0'; i++)
        {
            if (functions_buffer[i] == REVERSE)
            {
                // Switch state
                state = state ^ 1;
            }
            // Delete
            else 
            {
                // Reversed: 1, Normal: 0 
                head += state ^ 1;
                tail -= state;
            } 
        }

        int leftover_size = tail - head;
        if (leftover_size < 0)
        {
            printf("error\n");
        }
        else if (leftover_size == 0)
        {
            printf("[]\n");
        }
        else
        {
            // Parse input buffer, store it as int 
            int curr = 0;
            int tmp = 0; 
            for (int i = 1; input_buffer[i] != '\0'; i++)
            {
                if (input_buffer[i] == ',' || input_buffer[i] == ']')
                {
                    output_array[curr++] = tmp;

                    // Initialize tmp
                    tmp = 0;
                }
                // buf[i] is a digit
                else
                {
                    tmp = tmp * 10 + input_buffer[i] - '0';
                }
            }

            printf("[");
            if (state == REVERSED)
            {
                // Print backwards
                for (int i = tail - 1; i > head; i--)
                {
                    printf("%d,", output_array[i]);
                }
                printf("%d]\n", output_array[head]);
            }
            else 
            {
                for (int i = head; i < tail - 1; i++)
                {
                    printf("%d,", output_array[i]);
                }
                printf("%d]\n", output_array[tail - 1]);
            }
        }
    }
}

파이썬 풀이

어쩌다 파이썬으로 다시 풀게되어 기록.
빈 배열 처리에 주의한다.

import sys
from collections import deque

def apply_func(func: str, dq: deque) -> str:
    is_reversed = False
    for f in func:
        if f == 'R':
            is_reversed = not is_reversed
        else: # 'D' 
            if not dq:
                return "error"

            if is_reversed:
                dq.pop()
            else:
                dq.popleft()

    return "[" + ",".join(map(str, reversed(dq) if is_reversed else dq)) + "]"

if __name__ == "__main__":
    n_cases = int(sys.stdin.readline())
    input_data = iter(sys.stdin.read().split())
    get_token = lambda: next(input_data)

    out = []
    for _ in range(n_cases):

        func = get_token()
        arr_size = int(get_token())
        if (arr_size == 0):
            dq = deque()
            _ = get_token() # consume empty array
        else:
            dq = deque(map(int, get_token().strip("[]").split(',')))

        out.append(apply_func(func, dq))
    sys.stdout.write("\n".join(out))

재밌는 풀이

문제에서 주는 배열 문자열 형식이랑 같다보니 eval()을 쓰면 편하게 리스트로 변환해서 받아올 수 있다.
성능이나 안정성 측면에서 안좋은 방법인 것 같지만, 재밌어서 기록.

for _ in range(n_cases):

    func = get_token()
    arr_size = int(get_token())
    dq = deque(eval(get_token()))

    out.append(apply_func(func, dq))