[백준]5430(파이썬) - AC

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

5430번: AC

 

• 이 문제는 간단하지만 어떻게 시간을 줄일 거냐? 를 묻는 문제입니다.
• 저 같은 경우에는 일단 구현을 해놓고 짜 놓은 코드에서 어떻게 시간을 줄일지 생각을 합니다. 사람마다 맞는 방식을 찾는 게 중요한 것 같습니다.
• 구현은 어렵지 않았습니다. 최대한 for문을 안 쓰고 while과 deque를 사용해서 구현했고, 이 문제에서는 리스트 형식의 문자열을 입력값으로 받기 때문에 파싱을 해서 숫자가 들어있는 문자열로 바꾸는 부분이 중요했다고 생각합니다.
• 주요 구현은 R은 pop,popleftpop, popleft 그리고 D는 pop, popleft를 사용했는데요, 이 문제의 핵심! reverse를 q가 돌 때마다 실행해주면 당연히 시간 초과가 발생합니다.
• reverse를 쓰면서, 시간을 어떻게 줄일까? 생각하던 도중 두 번 뒤집으면 원래대로 돌아오는 성질을 이용했습니다.
  그러면 RDR은 어떻게 해? 중간에 맨 앞 원소를 뺴주면 바꿨을 때 순서가 다르잖아? 
  여기서 답이 나왔습니다. 한번 돌렸을 때 체크, 두번두 번 돌렸을 때 체크를 해주고 한번 돌렸을 때는 맨뒤 원소를, 두 번 돌려서 원상태로 돌아왔을 때는 맨 앞 원소를 제거해주면 되는 것이죠.
• 자세한 설명은 주석에서 확인해주시면 됩니다.

 

import sys,re
from collections import deque

input = sys.stdin.readline


# 1. deque reverse 와 deque.popleft() 사용
# 2. reverse를 사용은 하되 어떻게 최소화 할 수 있을지?
t= int(input())
for _ in range(t):
    p = str(input())
    num = int(input())
    # 문자열로 들어오기 때문에 마지막 괄호와 , 를 제외한  숫자 문자를 파싱해준다.
    number = deque(input().rstrip()[1:-1].split(","))
    # 0일 때는 아무것도 안넣은 리스트를 만들어준다.
    if num == 0:
        number = deque([])
    # 수행할 조건을 담은 deque를 만들어준다.
    p_q = deque(list(p.rstrip()))
    # R이 홀수이면 0 짝수이면 1이 되도록 flag를 만들어준다.
    flag = 0
    # 위에서 num이 0일 경우 error를 출력하기 위한 flag 
    empty_flag = 0
    while p_q:
        i = p_q.popleft()
        if i == 'D':
            if  not number:
                empty_flag = 1
            # flag 가 1이면 리스트 오른쪽 제거 ( 이후에 reverse 예정)
            elif number and flag == 1:
                number.pop()
            # flag 가 0 이면 리스트 왼쪽 제거 ( 이후에 reverse 안할 예정)
            elif number and flag == 0:
                number.popleft() 
        # 두번 바뀌면 안뒤집어 줘도 되고 빼주는 위치만 고려해주면된다.
        # 나중에 한꺼번에 Reverse 해야 시간초과가 발생하지 않는다.
        elif i == 'R' and flag == 0:
            flag = 1
        elif i == 'R' and flag == 1:
            flag = 0
        
    if empty_flag == 1:
        print("error")
    else:
        if flag == 1:
            number.reverse()
        # number에 str 형태로 들어가 있기 때문에 join을 해준다.
        print("[", end = "") 
        print(",".join(number), end = "") 
        print("]")