백준 - 5430번(덱,아이디어)

문제 내용 자체는 이해하기 어려운 문제가 아니라고 생각했고 이게 왜 골드 문제이지 싶었다.

하지만 개고생을 했다.

 

1. R을 받는 족족 reverse를 하게 되면 시간 초과가 난다.

2. 어떻게 하면 좋을까? 만약에 RR을 받는다고 가정해보자 이럴 경우 reverse를 하지 않아도 된다.

3. 그러나 이 문제를 reverse를 쓰려고 하는 순간 절대 못푼다.

4. D를 입력받으면 제일 앞의 원소를 제거한다는 것이 힌트이다.

5. 보통 D를 입력받으면 popleft()를 사용해서 원소를 제거할 것이다.

6. 생각해보면 reverse() 한 다음에 popleft()를 하는 것과 그냥 pop()을 쓰는 것과 동일한 효과라는 것이다.

7.  나는 그래서 key값이 홀수면 pop() 연산을 하고 짝수면 popleft() 연산을 하게 했다.

8. 마지막에 최종적인 key값이 홀수이면 연산이 다 수행된 리스트에 reverse함수를 적용했다.

9. 그리고 D를 입력받았을 때 and 배열의 길이가 0 이걸 둘 다 만족해야 error를 출력할 수 있다.

10. D를 입력받지 않고 배열의 길이가 0인 경우도 고려해야 한다. 이럴 땐 빈 리스트를 출력해야 한다.

 

상당히 고려할게 많게 함정이 많은 코드였다.

코드는 아래 다음과 같다.

 

import sys
import re
from collections import deque

n = int(sys.stdin.readline())
ans = []

for i in range(n):
    input = sys.stdin.readline()
    ###########배열 입력받기###########
    l = int(sys.stdin.readline())
    t_arr = sys.stdin.readline().rstrip()
    arr = deque()
    temp = re.findall('\d+', t_arr) #str배열에서 숫자만 추출

    for j in temp:
        arr.append(int(j))
    ################################
    key = 0 #R의 홀수 짝수 판별
    z = 0 #D를 입력받았는지 여부 확인
    for j in range(len(input)):
        if input[j] == 'R':
            key = key+1

        elif input[j] == 'D':
            if len(arr) == 0:
                ans.append('error')
                z = 1
                break

            elif key % 2 == 0 or key == 0:
                arr.popleft()

            elif key % 2 == 1:
                arr.pop()


    if len(arr) >= 0 and z != 1:
        if key % 2 == 1:
            arr.reverse()
        ans.append(list(arr))

for i in ans:
    i = str(i).replace(' ','') #띄어쓰기 제거
    sys.stdout.write(i+'\n')