[자료구조] 백준 1406번 에디터 with Python

https://www.acmicpc.net/problem/1406
왜 이문제가 실버 2일까~~ 했더니만 역시나 시간초과!!ㅎㅎ

import sys

s = sys.stdin.readline().rstrip()

c = len(s)

n = int(sys.stdin.readline().rstrip())

for i in range(n):
    com = sys.stdin.readline().rstrip()

    if ' ' in com:
        com, letter = com.split()

    if com == 'L':
        if c != 0:
            c -= 1

    elif com == 'D':
        if c != len(s):
            c += 1

    elif com == 'B':
        if c != 0:
            c -= 1
            s = s[:c] + s[c+1:]

    elif com == 'P':
        s = s[:c] + letter + s[c:]
        c += 1

print(s)

문자열 슬라이싱으로 풀어보기도 하고 리스트 insert, del을 사용해서도 풀어봤지만 시간초과가 났다.
insert와 del은 모두 O(N)의 시간복잡도를 가지고 있었고 상대적으로 시간복잡도가 작은 append와 pop을 사용해야했다.(append와 pop은 O(1))
append와 pop를 사용하기 위해선 스택을 두개로 나누어서 진행하면 된다.

import sys

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

n = int(sys.stdin.readline().rstrip())

for i in range(n):
    com = sys.stdin.readline().rstrip()

    if ' ' in com:
        com, letter = com.split()

    if com == 'L':
        if len(stack1) != 0:
            stack2.append(stack1.pop())

    elif com == 'D':
        if len(stack2) != 0:
            stack1.append(stack2.pop())

    elif com == 'B':
        if len(stack1) != 0:
            stack1.pop()

    elif com == 'P':
        stack1.append(letter)

print(''.join(stack1)+''.join(reversed(stack2)))