[백준] 5430 번 AC - python 파이썬

문제

처음 이 문제를 봤을 때는 간단하게 해결 할 수 있는 문제라고 생각했다.

그런데 조건을 보면 알겠지만 이 문제는 주어진 문제를 구현만 하는게 문제가 아니라 시간 최적화가 중요한 문제이다.

왜냐하면 n이 무려 10만 이하의 수이기 때문이다.

그렇기때문에 단순히 R이 나올때마다 정렬을 한다면 무조건 시간초과다...(처음에 이렇게 풀었다가 채점이 너무 오래 걸려서 렉걸린줄 알았다 ㅎ)

아무튼 그렇기 때문에 단순히 리스트가 아닌 queue 를 이용해서 풀어줬다.

이때 순서를 바꾸는 행위를 R이 나올때마다 하지 않고 R이 짝수개 나오면 그대로 홀수개라면 순서 변환 되는 것을 이용해서 풀어주었다.

나의 코드

from collections import deque
import sys

input = sys.stdin.readline

T = int(input())

for _ in range(T):
    p = input().rstrip() 
    n = int(input())  
    arr = input().rstrip()[1:-1] 

    if arr:
        arr = deque(arr.split(","))
    else:
        arr = deque()
    
    reverse = False  # 배열의 뒤집힘 상태
    error = False  # 에러 발생 여부

    for cmd in p:
        if cmd == 'R':
            reverse = not reverse
        elif cmd == 'D':
            if arr:
                #D 이전에 R의 개수가 홀수개라서 순서가 바뀌어야 한다면 오른쪽끝에서 빼기
                if reverse:
                    arr.pop()
                #순서가 안바뀌는 경우이므로 앞에서 빼주면 됨
                else:
                    arr.popleft()
            else:
                error = True
                break
    if error:
        print("error")
    else:
        if reverse:
            arr.reverse()  # R이 홀수 개 나왔을 때
        print("[" + ",".join(arr) + "]")

단순히 문제를 해결해주는 것 보다 시간을 최적화 할 수 있는 방법을 찾는게 더 어려운 것 같다