[백준 5430 파이썬] AC (골드 5, 덱)

알고리즘 유형 : 덱
풀이 참고 없이 스스로 풀었나요? : O

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

소스 코드(파이썬)

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

for _ in range(int(input())):
    p = input().rstrip().replace("RR", "") # 연속 2번 뒤집는건 결국 그대로란 뜻이니 이걸 모두 없애주자
    n = int(input())
    arr = []
    if n == 0:
        input() # 입력값을 받아만 두고, arr에는 빈 리스트 직접 할당해둔거 그대로 두기
    else:
        arr = [*map(int, input().rstrip()[1:-1].split(","))] # 괄호 지우고 숫자만 골라 int list로 저장
    q = deque(arr)
    is_occured_error = False
    is_reversed = False
    
    for cmd in p:
        if cmd == "R":
            # 시간복잡도 향상을 위해 직접 뒤집지않고, 원소를 꺼내는 방향만 바꿔주기 위해
            # 뒤집어졌는지 여부를 나타내는 is_reversed 변수 활용
            is_reversed = False if is_reversed else True
        elif cmd == "D":
            if q:
                if is_reversed:
                    q.pop()
                else:
                    q.popleft()
            else:
                is_occured_error = True
                break
    
    if is_occured_error:
        print("error")
    else:
        if is_reversed:
            q.reverse() # 덱에 남아있는 원소를 출력할 때는 뒤집어진 상태를 실제로 반영해줘야함
        
        print("[" + ",".join(map(str, q)) + "]")

풀이 요약

1. 단순히 생각하면 배열을 리스트에 저장한 후, 이걸 직접 뒤집어가면서 한쪽 방향으로만 pop을 해준다거나, 덱에 저장 후 직접 뒤집어가면서 popleft만 실행해주면 될 것 같다.

   하지만 n도 10만까지고 p도 10만까지이다.

   p가 R이 10만개로 이루어진 문자열일 경우에, n도 10만이라면 이 때의 시간복잡도는 $10^{10}$이나 되버린다.

   즉, 뒤집는 행위를 시간복잡도를 고려하여 구현하는 것이 문제의 핵심이다.

2. 덱을 활용하면 해결할 수 있다.

   우선 그 전에 p에 들어있는 "RR"을 모두 제거한다. 연속으로 2번 뒤집으면 결국 그대로기 때문에 의미없는 시간 낭비 명령어이다. replace로 전처리해주자.

3. 배열을 덱에 넣는다. 이 때 R 명령어가 들어왔을 경우 직접 뒤집지말고, pop을 왼쪽에서 해줄지 오른쪽으로 해줄지만 바꿔주자.

   R이 들어올때마다 is_reversed의 값을 바꾸고, 이 값에 따라 pop을 할지 popleft를 할지만 정해주면 조건에 맞게 D를 수행할 수 있게 된다.

4. 다만 결과를 출력할 때는, 뒤집어졌는지의 여부가 덱의 원소에 실제로 반영되어있어야하므로, 마지막에는 is_reversed가 True라면 실제로 reverse()로 뒤집어주자.

배운 점, 어려웠던 점

• 직접 뒤집지 않고도 D 명령어를 유효하게 수행할 수 있게 구현하는 아이디어를 떠올리는데 시간이 좀 걸렸다. 이 문제를 풀면서, 문제의 핵심이 뭔지 파악하고 거기에 집중적으로 시간을 쏟는 노하우가 조금 생긴 것 같아서 아주 유익했다.