[Python] 백준 1406 에디터 풀이

# PROBLEM - 에디터
# TIER - S2
# NUMBER - 1406
# DATE - 2022-08-02 19:31
# IDEA - 아이디어의 중요성을 알려준 문제이다.

# 이게 처음에 별 생각없이 insert(N, "어쩌구"), pop(N) (시간복잡도 O(N))
# 이런걸로 구현하다가 시간초과 나서 풀이를 찾아봤는데
# 리스트1 리스트2 이런식으로 만들고 리스트2는 나중에 뒤집에서 출력하던데
# 나는 이게 싫어서 popleft, appendleft 가 있는데다가
# 시간복잡도 O(1)인 deque 써서 직관적으로(안뒤집고) 풀이했다

# 풀이의 핵심은
# left [cursor] right
# 이런식으로 커서의 위치를 int형으로 구현한게 아니라
# 커서 기준으로 좌측, 우측으로 잘라서 수정삭제를 했다.
# 이렇게 하면 커서기준 오른쪽 연산이
# popleft, pop, append, appendleft 통해서 O(1)만에 가능함

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

left = deque(input().rstrip())
right = deque()
N = int(input().rstrip())
length = len(left)


for i in range(N):
    order = list(map(str, input().split()))
    if order[0] == "P":
        left.append(order[1]) # 커서 좌측에 요소 추가
    if order[0] == "L":
        if len(left) != 0: # left 배열이 존재하는 경우
            right.appendleft(left.pop()) # left의 가장 우측 원소를 right의 가장 좌측으로 옮김 (커서의 움직임 구현1)
    if order[0] == "D":
        if len(right) != 0:  # right 배열이 존재하는 경우
            left.append(right.popleft()) # right의 가장 좌측 원소를 left의 가장 우측으로 옮김 (커서의 움직임 구현2)
    if order[0] == "B":
        if len(left) != 0: # 커서 좌측에 삭제할게 있으면
            left.pop() # 삭제하셈

print("".join(left + right))  # 리스트 합치고 쪼인으로 붙여서 출력