백준 - AC / Gold 5 / 5430번 / Python

문제 📋

백준 - AC

풀이 📝

import sys
from collections import deque


def solution(n, arr, cmds):
    is_reverse = False
    q = deque(arr)

    for cmd in cmds:

        if cmd == "R":
            if is_reverse:
                is_reverse = False
            else:
                is_reverse = True
        elif cmd == "D":
            if not q:
                return "error"

            if is_reverse:
                q.pop()
            else:
                q.popleft()
    if is_reverse:
        q.reverse()

    return str(list(q))


t = int(sys.stdin.readline())

for _ in range(t):
    cmds = list(sys.stdin.readline())
    n = int(sys.stdin.readline())
    arr = sys.stdin.readline().rstrip()[1:-1].split(',')

    if arr[0] == "":
        arr = []
    else:
        arr = map(int, arr)

    print(solution(n, arr, cmds).replace(" ", ""))

테스트케이스 개수인 t은 최대 100이고
명령어의 개수가 최대 100,000이며
배열의 길이가 최대 100,000이기 때문에

명령어를 순회하는 것까지는 시간 초과가 나지 않는다.
하지만 배열을 뒤집는 reverse() 함수는 시간 복잡도가 O(N)이기 때문에
실제로 배열을 뒤집게 되면 시간 초과가 난다.

따라서 실제로 배열을 뒤집지 않고 flag을 둬서
배열을 뒤집은 것처럼 가정하고 queue에서 pop()을 했다.