[BACKJOON] stack 문제

1406 에디터

실패 : 시간초과

파이썬 list()에서 remove()나 insert()는 리스트 원소의 위치의 탐색까지 시간이 걸려서 O(n) 시간의 복잡도를 가진다.

해결 : 끝이 마주보는 stack 2개 이용

stack이라는 자료구조는 한쪽만 열려있어서 O(1)의 시간 복잡도를 가지기에 시간 초과 문제를 해결할 수 있다.

import sys

stack = list(sys.stdin.readline().rstrip())
stack2 = list()

n = int(sys.stdin.readline())
for _ in range(n):
    value = sys.stdin.readline().rstrip()
    if value == 'L':
        if stack != []:
            stack2.append(stack.pop())
    elif value == 'D':
        if stack2 != []:
            stack.append(stack2.pop())
    elif value == 'B':
        if stack != []:
            stack.pop()
    elif value[0] == "P":
        stack.append(value[-1])

print(''.join(stack), end='')
print(''.join(reversed(stack2)))

위 문제에서는 커서의 위치 이동과 커서 왼쪽의 문자 삽입/삭제가 동작해야한다.

1. 커서를 마주 보는 2개의 stack 중간이라고 생각한다.

2. 각 경우에 따라 다르게 동작

   • 왼쪽으로 이동 : 왼쪽 stack의 요소를 오른쪽 stack에 삽입
   • 오른쪽으로 이동 : 오른쪽 stack의 요소를 stack에 삽입
   • 왼쪽 문자 삭제 : 왼쪽 stack의 마지막 요소 제거
   • 왼쪽에 문자 삽입 : 왼쪽 stack에 요소 추가

   위에서 언급한 stack의 요소는 각 stack의 top 부분의 문자를 의미함

---