[백준] 5430번 AC - 파이썬

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

5430번: AC

풀이

전제조건

명령어는 R과 D가 주어진다.

R은 주어진 문자열을 뒤집는 것을 뜻한다. D는 주어진 문자열의 첫번째 요소를 지우는 것을 뜻한다.

다만, 문자열이 공백일 경우 D를 사용하면 코드는 error를 출력하며 중단한다.

 

목표: 주어진 실행어를 거친 문자열의 결과를 출력하는 것

 

여기까지는 단순한 구현이라 생각할 수 있지만, 코드를 단순히 리스트를 이용해서 풀어준다면 시간초과가 일어난다.

 

주의) 시간초과가 일어나는 이유

* R이 나올 경우 문자열을 뒤집을 때 매번 뒤집을 때마다 O(N)의 시간을 소모하기에 시간초과가 일어난다.

이를 해결하기 위해서는 문자열을 뒤집지않아도 코드 안에서 뒤집은 것처럼 행동을 하게 만들면 됩니다.

R이 나올때마다 문자열의 뒤집힘을 기억해주는 정수형 변수에 1씩 더해줍니다. 나중에 D실행어나 출력을 할 때 이 정수형 변수를 2로 나눈 나머지를 이용해서 상황에 맞는 popleft()와 pop()을 사용해주면 됩니다.

 

예시)

뒤집힘을 저장하는 정수형 변수 => cnt

cnt % 2 = 0일 경우 문자열은 처음 주어진 방향으로 나열되어있습니다.

cnt % 2 = 1일 경우 문자열은 처음 주어진 방향과 반대 방향으로 나열되어있습니다.

import sys
from collections import deque
t = int(input())

# 실행어에 따른 문자열 처리
def use_function(queue, order):
    rev = 0
    for i in order:
        if i == "R":
            rev += 1
        elif i == 'D':
            if len(queue) == 0:
                return "error"
            else:
           		# 뒤집히지않았을 경우 popleft()로 첫문자를 제거해준다.
                if rev% 2 == 0:
                    queue.popleft()
                    
                # 뒤집혔을 경우 pop()로 첫문자를 제거해준다.
                else:
                    queue.pop()
	
    # 출력처리를 하기 위해 뒤집혔는지 확인한 뒤에 상황에 맞게 출력한다.
    if rev % 2 == 0:
        return f'[{",".join(queue)}]'
    else:
        queue.reverse()
        return f'[{",".join(queue)}]'

for _ in range(t):
    order = sys.stdin.readline().rstrip()
   	# 2번의 일련된 R실행은 다시 제자리로 찾아오기에 삭제해준다.
    order = order.replace('RR', '')
    n = int(sys.stdin.readline())
    nums = deque(sys.stdin.readline().rstrip()[1:-1].split(","))
    
    # 문자열이 아무것도 주어지지않았을 경우. 직접 deque를 비워준다.
    if n == 0:
        nums = deque([])
    print(use_function(nums, order))

출력결과