[BOJ][Python]5430번 풀이

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

5430번: AC

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

t = int(ssr())
for _ in range(t):
    p = ssr().rstrip()
    n = int(ssr())
    state = 1
    if n == 0:
        num = ssr().rstrip()
        num = deque([])
    else:
        num = ssr().rstrip()
        num = deque(num[1:-1].split(','))
    for i in p:
        if i == 'R':
            state *= -1
        else:
            if len(num) == 0:
                state = 0
                break
            else:
                if state == 1:
                    num.popleft()
                else:
                    num.pop()
    if state == 1:
        ans = '[' + ','.join(num) + ']'
        print(ans)
    elif state == -1:
        num.reverse()
        ans = '[' + ','.join(num) + ']'
        print(ans)
    else:
        print('error')

이번 문제는 정말 파이썬 공부할 때 초반에 좀 쓰다가 너무 안써서 까먹었던 명령어들을 잔뜩 쓰는 문제였습니다. reverse가 반환이 없다는 사실도 까먹고 바보짓을 하지를 않나 join은 어떻게 쓰는지 기억도 안나고 리스트 슬라이싱까지... 간만에 보는 기능들이라 반가웠네요.

 

문제 접근은 이렇습니다. 문제가 시키는대로 R이 나올 때 마다 reverse를 사용했다간 가볍게 시간초과를 해버릴 겁니다. 한 두번은 괜찮을지 모르겠지만 p의 최대 길이가 100000이고 n도 마찬가지이기 때문에 가령 p가 'R'*100000이라면 O(N)짜리 알고리즘을 100000번 돌리는 셈이 되겠죠. 아마 시간초과를 겪는 분들은 다 이래서 시간초과가 나셨지 않았을까하고 추측해봅니다. 그래서 저는 deque를 이용해서 R이 한 번 나올 때 마다 state를 반전시켜서 popleft와 pop을 state에 따라 사용하도록 코드를 작성했습니다. 그렇다면 RDRDRDRDRDRDRDR이런식으로 명령이 주어지더라도 배열 순서를 바꾸지 않으면서 바꾼것처럼 이용할 수 있으니까요. 그리고 마지막에 출력하기 전에 state를 보고 R이 짝수 번 나왔다면 처음 설정했던 값일테니 그대로, 홀수 번 나왔다면 -1일 테니 한 번 뒤집어 주고 출력하는 것으로 마무리했습니다. 길이가 0번일 때는 정상적인 pop과정에서 나올 수 없는 값으로 state를 바꿔준 다음 마지막에 체크해서 error를 출력하도록 했습니다.

 

엄청 어려운 문제는 아닙니다만 약간 신경을 써줘야 했던 문제가 아닌가 싶네요. 구현 문제의 특징을 잘 가지고 있는 문제가 아닐까 싶네요.