백준 5430 풀이 (AC, 큐, 파이썬)

이번 문제는 은근히 손이 가는 문제였다. 문제 자체가 어렵지는 않다. 

R함수와 D함수에 맞춰 역할을 해주면 될뿐이다. 다만 시간제한이 1초이기 때문에 최대한 효율적으로 만들어 주어야 한다. 따라서 여러 조건에 맞추어 불필요한 부분을 제거하거나 트릭을 써주면 된다.

 

1. R이 R과 붙어있는 경우 제거해준다. (거꾸로 2번하면 원상태이기 때문)

2. opcode에 존재하는 D의 개수와 실제 주어지는 값의 개수 비교

3. R의 여부에 따라 앞을 뽑아낼지 뒤를 뽑아낼지 결정 (왜냐하면 실제 q를 거꾸로 배열해서 연산을 하려고 하면 큐의 크기가 큰 경우 시간이 오래걸린다. 그래서 굳이 reverse()를 쓰지 않고 앞을 뺄지 뒤를 뺄지 결정하는 것이다.)

4. 마지막에 출력방향을 결정하여 출력.

 

이때 살짝 어려웠던게 1,2번을 구현하는게 어려웠다. RR을 제거하면서 D의 개수를 찾아주었는데 동시에 하다보니 한번은 오답을 제출했다.

R의 여부에 따라 디폴트값은 왼쪽이다가, R을 한번 만나면 오른쪽으로 변경해주는 방식으로 진행했다.

 

덕분에 코드는 상당히 더럽지만 어쨌거나 풀리긴 했다. 원리는 어렵지 않았으나 디테일한 부분이 귀찮았다.

from collections import deque
import sys
n = int(sys.stdin.readline())
def opcheck(opcode):
    i = 0
    count = len(opcode)
    while i < len(opcode)-1:
        if opcode[i] == 'R' and opcode[i+1] == 'R':
            opcode.pop(i)
            opcode.pop(i)
            count -= 2
            continue
        else:
            if opcode[i] == "R":
                count -= 1
            i+=1
    if len(opcode) != i:
        if opcode[-1] == 'R':
            count -= 1
    return opcode,count

for _ in range(n):
    op = list(sys.stdin.readline()[:-1])
    op,d = opcheck(op)
    n = int(sys.stdin.readline())
    tmp = input()
    if len(tmp) == 2:
        q = []
    elif len(tmp) > 2:
        q = deque(list(map(int, tmp[1:-1].split(','))))
    if n < d:
        print("error")
        continue
    direct = 0
    for i in op:
        if i == "R":
            direct ^= 1
        else:
            if direct == 0: #정방향
                q.popleft()
            else:#역방향
                q.pop()
    if direct != 0: #역방향
        q.reverse()
    print(str(list(q)).replace(" ",""))