Baekjoon Online Judge 1406번 파이썬

문제 링크
https://www.acmicpc.net/problem/1406

1406번: 에디터

처음에 잘못 짠 코드

import sys

string = list(sys.stdin.readline().rstrip())
M = int(sys.stdin.readline().rstrip())

N = len(string)
cursor = len(string)

for i in range(M):
  command = list(sys.stdin.readline().split())
  if command[0]  == "L":
    if cursor != 0:
      cursor -= 1
  elif command[0] == "D":
    if cursor < len(string):
      cursor += 1
  elif command[0] == "B":
    if cursor > 0:
      string.remove(string[cursor-1])
      cursor -= 1
  elif command[0] == "P":
    string.insert(cursor,command[2])
    cursor += 1

for s in string:
    print(s, end="")

이렇게 짰더니 시간 초과가 나왔다.

그래서 다른 사람들의 풀이를 찾아보았고 풀이를 이해하고 제출하였다.

위에서 사용한 insert, remove의 시간 복잡도는 O(N)이다. 이 메서드들을 사용해서 시간 초과가 나왔기 때문에,
시간 복잡도가 O(1)인 append, pop을 사용해야 한다.

내가 이해한 방법

정답 코드

import sys

stack1 = list(sys.stdin.readline().rstrip())
stack2 = []
M = int(sys.stdin.readline().rstrip())

for i in range(M):
  command = list(sys.stdin.readline().split())
  if command[0]  == "L":
    if stack1:
      stack2.append(stack1.pop())
  elif command[0] == "D":
    if stack2:
      stack1.append(stack2.pop())
  elif command[0] == "B":
    if stack1:
      stack1.pop()
  elif command[0] == "P":
      stack1.append(command[1])

stack = stack1 + list(reversed(stack2))

print("".join(stack))