https://www.acmicpc.net/problem/1406
실패이유 : 시간초과
import sys
front_stack = list(sys.stdin.readline().rstrip())
back_stack = []
N = int(sys.stdin.readline().rstrip())
for _ in range(N):
buf = list(sys.stdin.readline().rstrip().split())
ins = buf[0]
if ins == 'P':
front_stack.append(buf[1])
elif ins == 'L':
if front_stack:
back_stack.append(front_stack.pop())
elif ins == 'D':
if back_stack:
front_stack.append(back_stack.pop())
elif ins == 'B':
if front_stack:
front_stack.pop()
front_stack.extend(reversed(back_stack))
print("".join(front_stack))
insert(idx, value),pop(idx)는 최악의 경우 O(n) 시간 복잡도- 명령어의 개수만큼 for문을 반복, 따라서 최종적인 시간 복잡도는 O(n^2)
- 시간초과 발생
- 커서 앞 문자들은
front_stack에 보관, 커서 뒤 문자들은back_stack에 보관
pop(),append()는 O(1) 시간 복잡도
- 최종적인 시간복잡도 O(n)
back_stack에 문자들은 커서에서 가까운 것이 나중에 들어간다.
- 마지막에 하나의 문자열로
front_stack과 합칠 때reversed(back_stack)처리
