[백준] 5430 AC (python)

1. 문제

https://www.acmicpc.net/problem/5430

2. 풀이

스택을 생성 후 R인 경우 뒤집고 D인 경우 popleft하는 방식이다.
초기에 reverse()를 사용해 R이 나올때 마다 뒤집는 방식의 코드를 구현하였고 O(n)의 시간이 문자열의 길이만큼 걸리게 되어 시간초과가 나왔다.
그래서 boolean을 통해 뒤집혀졋는지 아닌지를 체크만하고 이에 따라 popleft와 pop을 사용한 후 마지막에 뒤집는 방식을 사용하였다. 시간복잡도 O(n) 이 걸려 해결할 수 있었다.

3. 코드

import sys
from collections import deque

t = int(input())

for _ in range(t):
    ans = []
    p = sys.stdin.readline().strip()
    n = int(sys.stdin.readline())
    temp = sys.stdin.readline().strip()
    isReverse = False

    if n == 0:
        arr_list = deque()
    else:
        arr_list = temp[1:len(temp)-1].split(',')
        arr_list = deque(arr_list)

    for char in p:
        if char == 'R':
            isReverse = not isReverse
        elif char == 'D':
            if arr_list:
                if isReverse:
                    arr_list.pop()
                else:
                    arr_list.popleft()
            else:
                ans.append('error')
                break

    if len(ans) == 0:
        if isReverse:
            arr_list.reverse()

        print('[' + ','.join(map(str, arr_list)) + ']')
    else:
        print(*ans)
        

이전 시간 초과 코드

import sys
from collections import deque

t = int(input())

for _ in range(t):
    ans = []
    p = sys.stdin.readline().strip()
    n = int(sys.stdin.readline())
    temp = sys.stdin.readline().strip()
    if n == 0:
        arr_list = deque()
    else:
        arr_list = temp[1:len(temp)-1].split(',')
        arr_list = deque(arr_list)

    for char in p:
        if char == 'R':
            arr_list.reverse()
        elif char == 'D':
            if arr_list:
                arr_list.popleft()
            else:
                ans.append('error')
                break

    if len(ans) == 0:
        print('[' + ','.join(map(str, arr_list)) + ']')
    else:
        print(*ans)```