코테 백준 5430 골드5

백준 5430

처음에는 문제 그대로 따라가면서 풀었다.

import sys
from collections import deque
input=sys.stdin.readline

for i in range(int(input())):
    p=input().rstrip()
    n=int(input())
    x=deque(input().rstrip()[1:-1].split(','))
    flag=0
    if n==0:
        x=deque()
    for i in p:
        if i=='R':
            x.reverse()
        elif i=='D' and x:
            x.popleft()
        elif i=='D' and not x:
            print('error')
            flag=1
            break
    if flag==0:
        print('['+','.join(x)+']')

시간초과라는 결과가 떴다. 그이유가 입력값이 'R'일때 마다 계속 reverse()함수를 호출해서 그렇다. 그럼 시간복잡도가 최소 O(N^2)이므로 그런결과를 보였다. 그래서 이점을 보완하자고 생각해서 시작과 끝점을 변수로 설정해서 해보면 어떨까라고 생각했는데 그럼 deque를 사용하는 이유가 없어지고 시작점과 끝점을 바꾸고 또 상황에 따라 끝점을 한칸 앞으로할지 시작점을 한칸 앞으로 할 지 복잡했다.

그래서 reverse를 0으로 두고 한번 역전이 일어나면 reverse를 1증가했다. 그래서 최종 reverse를 2로 나누어 0이면 사실 상 그대로이고 나머지가 1이면 최종 1번만 역전된것이다. 만약 삭제가 일어날때 revert의 나머지가 0이면 popleft, 1이면 pop을 사용해주면된다.

개인적으로 이문제의 핵심은 reverte를 2로 나누어 나머지를 이용한것이다

import sys
from collections import deque
input=sys.stdin.readline

for i in range(int(input())):
    p=input().rstrip()
    n=int(input())
    x=deque(input().rstrip()[1:-1].split(','))
    reverte=0
    flag=1
    if n==0:
        x=[]
    for i in p:
            if i=='R':
                reverte+=1
            elif i=='D' and len(x)<1:
                flag=-1
                print('error')
                break
            elif i=='D' and reverte%2==0:
                x.popleft()
            elif i=='D' and reverte%2!=0:
                x.pop()
    if flag==1:
        if reverte%2==0:
            print('['+",".join(x)+']')
        else:
            x.reverse()
            print('['+",".join(x)+']')