백준 1406 에디터 파이썬

 

문제 풀이

 

첫 번째 시도

for _ in range(M):
    t = list(map(str, sys.stdin.readline()))
    if t[0] == 'L' and cursor != 0:
        cursor -= 1
    elif t[0] == 'D' and cursor != len(N):
        cursor += 1
    elif t[0] == 'B' and cursor != 0:
        del N[cursor - 1]
        cursor -= 1
    elif t[0] == 'P':
        N.insert(cursor, t[2])
        cursor += 1

시간 초과가 나왔다.

insert와 del을 썼는데, 시간복잡도가 O(n)이어서 그런 것 같았다.

 

 

 

 

두 번째 시도

시간복잡도 O(1)인 append, pop을 써서 다시 시도!

커서를 옮길 때 cursor 변수를 옮기는 게 아니라,

왼쪽 스택, 오른쪽 스택을 나눠서 커서가 옮겨질 때마다 스택에서 pop, append를 하는 것이다.

예를 들어, 커서를 왼쪽으로 한 칸 옮긴다면 왼쪽 스택에서 pop하고 그 문자를 오른쪽 스택에 append 한다. 커서를 오른쪽으로 옮긴다면 반대로 하면 된다.

import sys

N = list(map(str, sys.stdin.readline().rstrip()))
N2 = []
M = int(sys.stdin.readline())


for _ in range(M):
    t = sys.stdin.readline().rstrip()
    if t[0] == 'L' and N:
        N2.append(N.pop())
    elif t[0] == 'D' and N2:
        N.append(N2.pop())
    elif t[0] == 'B' and N:
        N.pop()
    elif t[0] == 'P':
        N.append(t[2])

N2.reverse()
print(''.join(i for i in N), end='')
print(''.join(i for i in N2))