파이썬 백준 1406번: 에디터

문제

https://www.acmicpc.net/problem/1406

1406번: 에디터

 

풀이

처음에 insert를 사용하니 시간초과가 발생했다. 

import sys
input_string=list(sys.stdin.readline().strip())
cursor=len(input_string)
N=int(sys.stdin.readline())
for _ in range(N):
    command=sys.stdin.readline().strip()
    if 'P' in command:
        new=command.split(' ')[1]
        input_string.insert(cursor,new)
        cursor +=1
    elif 'L' in command:
        if cursor>0:
            cursor -=1
    elif 'D' in command :
        if cursor < len(input_string):
            cursor +=1
    elif 'B' in command :
        if cursor>0:
            input_string.pop(cursor-1)
            cursor-=1
print(*input_string, sep='')

 

append()와 pop() 는 시간복잡도가 O(1) 인데 비해 insert()는 O(N)이다.

따라서 append와 pop만을 사용하기 위해 커서 앞쪽, 뒤쪽 stack을 각각 따로 구현했다. 

import sys

front_cursor=list(sys.stdin.readline().strip()) #처음에는 모두 커서 앞쪽에 존재
back_cursor=[]

N=int(sys.stdin.readline())
for _ in range(N):
    command=sys.stdin.readline().strip()
    if 'P' in command:
        new=command.split(' ')[1]
        front_cursor.append(new)#커서 앞쪽에 추가

    elif 'L' in command:
        if len(front_cursor)!=0:
            back_cursor.append(front_cursor.pop()) #커서앞쪽에 있던 값을 커서 뒤쪽으로 옮김
    elif 'D' in command :
        if len(back_cursor) != 0:
            front_cursor.append(back_cursor.pop()) #커서 뒤쪽에 있던 값을 커서 앞쪽으로 옮김
    elif 'B'  in command :
        if len(front_cursor) != 0:
            front_cursor.pop() #커서앞쪽의 문자 삭제
print(*front_cursor, sep='',end='')
back_cursor.reverse() #커서 뒤쪽의 경우 출력시 reverse해줌
print(*back_cursor, sep='')