[Deque] 백준 Gold5 5430 AC

문제

https://www.acmicpc.net/problem/5430

 

---

설계 ✨

문제에서 p와 n 범위를 보았을 때 for문으로 하나씩 돌아가면서 풀면 시간초과가 발생할 것으로 파악되었다.

그래서 어떤 방법이 있을까 생각해보다가 dp는 조건에 맞지 않고, 투포인터로 문제를 풀어야하나 고민하던 와중에

R이 2번, 4번, 6번...이면, 원래 배열과 같다는 것을 일단 파악하였다.

그렇다면 R일때 카운트를 증가시키고, D일때  카운트가 홀수이면 뒤에서 빼고, 카운트가 짝수이면 앞에서 빼면 되겠다고 생각하였다. 

이 과정에서 deque의 popleft() (앞에서 빼기) , pop() (뒤에서 빼기)을 생각하여 deque를 이용하였다. 

 

 

또 이 문제에서 중요한 포인트는 예제 입력 중 '[1,2,3,4]'와 같이 입력받는 것을 어떻게 처리하는지이다. 

input()말고 속도가 더 빠른 sys.stdin.readline()을 사용하였는데, input()과 다르게 개행문자 '\n'을 포함하기 때문에 오른쪽 공백을 제거해줘야한다. rstrip()으로 오른쪽 공백을 제거하였다.

그리고나서, 첫번째 요소 '['와 맨 마지막 요소 ']'을 제거해주기 위해 [1:-1]로 슬라이싱하였다. 

','을 구분자로 요소를 나눠주기위해 split을 사용하였고, 이때 빈 문자열인데 split을 하면 [''] 이런 경우가 나올 수 있기 때문에 예외처리를 해주었다.  ['']는 빈리스트가 아니라 길이가 1인 리스트가 되기 때문에 꼭 처리가 필요하다. 

 

 

이렇게 문제를 다 풀고나서 제출하였는데, 백준에서 출력초과라는 오류가 발생했다. 

예제 출력에서 보면 [1,2,3,4]와 같이 리스트 형식으로 출력되어서 리스트로 반환시켰는데, 이러면 출력초과가 발생한다.

문자열로 바꿔서 반환해주었더니 문제가 해결되었다. 

 

 

 

def ac(p, number_list):
    cnt = 0
    for i in range(len(p)):
        if p[i] == 'R':
            cnt += 1  # 배열의 뒤에서 원소를 빼야하므로 카운트 하나씩 증가

        else:
            if not number_list:
                return "error"
            else:
                if cnt % 2 == 0: # cnt가 짝수이면 원래 배열이므로
                    number_list.popleft() # 원래의 배열에서 앞에서 수를 빼기
                else: # cnt가 홀수이면 배열을 뒤집에서 앞에서 빼는 것이므로
                    number_list.pop() # 원래의 배열에서 뒤에서 수를 빼기 


    if cnt % 2 != 0:
        number_list.reverse()

    return '[' + ','.join(number_list) + ']' # 출력초과 해결: 리스트를 문자열로 출력


from collections import deque

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

for i in range(t):
    p = sys.stdin.readline().rstrip() # 오른쪽 공백 제거
    n = int(sys.stdin.readline()) 

    # 리스트 입력 처리가 관건!
    number_list = sys.stdin.readline().rstrip()[1:-1] # 끝에 '['랑 ']' 없애기

    if len(number_list) > 1: # ['']의 길이는 1 예외처리
        number_list = number_list.split(",")
    number_list = deque(number_list)

    print(ac(p,number_list))