(Python)백준 코딩테스트 연습 - 에디터(1406)

1. 문제

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

1406번: 에디터

2. 풀이

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

# leftStack, rightStack : 커서 기준 왼쪽 스택과 오른쪽 스택
leftStack = deque(list(input().strip()))
rightStack = deque()
# print("leftStack :", leftStack)
# print("rightStack :", rightStack)

# orderCnt : 명령어 수
orderCnt = int(input())

for i in range(orderCnt):
    order = input().strip()
    if "L" in order and len(leftStack) > 0:
        rightStack.appendleft(leftStack.pop())
    elif "D" in order and len(rightStack) > 0:
        leftStack.append(rightStack.popleft())
    elif "B" in order and len(leftStack) > 0:
        leftStack.pop()
    elif "P" in order:
        add_str = order.split(" ")[1]
        leftStack.append(add_str)
leftStack.extend(rightStack)
print("".join(leftStack))

3. Feedback

 - 이 문제는 거의 1주일간 고민을 했던 문제이다.

 처음에는 deque 하나만을 사용하여 해결하려 하니 시간 초과가 발생하였다.

 해결을 위해 다른 방법을 찾던 중 연결 리스트를 사용해서 해결을 시도해 보게 되었다.

 처음에는 단방향 연결리스트를 사용하였는데 이전 노드의 위치를 찾을때 일일이 조회하다 보니 시간 초과가 발생하였고,

그래서 수정한 연결리스트인 양방향 연결리스트를 사용하였는데도 시간 초과가 발생하였다.

 어떻게해야 시간 초과를 해결할 수 있을까 고민하던 중 커서의 위치를 두 deque를 분리하는 방법으로 표현하면 어떨까라는 생각을 하게 되었고, 위와 같이 코드를 구성하여 해결할 수 있었다.