AC - 5430번

입력받는 배열을 파싱한 후 deque로 변환하여 다루면 빠른 속도로 해결할 수 있다.

deque의 속도는 O(1) 이고, 리스트의 속도는 O(n)이기 때문이다.

하지만 deque의 reverse(deque.reverse())는 속도가 리스트의 reverse와 비슷하게 느리다.

따라서 deque로 구현하되 reverse를 최대한 적게 사용하는 방법으로 코드를 짜야한다.

 

문제에서 입력받는 수행할 함수 p에서 R이 나올 때 마다 reverse를 하지말고,

상황에 따라서 deque.pop()과 deque.popleft()를 적절하게 사용해주면 된다.

그리고 deque.reverse()는 가장 마지막에 검사하여 적용해주면 된다.

from collections import deque
import sys

n = int(input())
for _ in range(n):
    order = input()
    dq_len = int(input())
    raw_dq = list(input()[1:-1].split(','))
    dq = deque()
    for i in raw_dq:
        dq.append(i)

    result = ''
    reverse = False
    for i in order:
        if i == 'R':
            reverse = not reverse
        elif reverse and dq!=deque(['']) and len(dq)>0:
            dq.pop()
            
        elif not reverse and dq!=deque(['']) and len(dq)>0:
            dq.popleft()
            
        else:
            result = 'error'
            print('error')
            break
    if reverse:
        dq.reverse()
    dq = f'[{",".join(dq)}]'
    if result != 'error':
        print(dq)

참고자료 : 

https://stackoverflow.com/questions/73140702/why-is-pythons-deque-reverse-so-slow

Why is python's deque.reverse() so slow?