[백준] 1406 에디터 (파이썬 python)

 

 

문제 링크

 

 

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

1406번: 에디터

 

 

문제

 

 

 

 

 

문제 풀이

 

 

insert, remove를 이용해 간단하게 풀려고 시도해봤지만

시간 초과가 나타났다. 문제에 나타난 입력 개수가 많기 때문에 시간을 잘 고려해야한다.

insert, remove 대신에 append, pop을 이용하면 시간복잡도를

O(N)에서 O(1)까지 줄일 수 있다.

아이디어를 찾기 어려워 나도 블로그를 많이 찾아봤는데 너무 좋은 아이디어가 있어 참고했다!

스택을 이용한 풀이로, st_left는 커서의 왼쪽, st_right는 커서의 오른쪽이 된다.

만약, L을 입력받아 커서가 왼쪽으로 이동할 경우 st_left의 마지막 요소가 pop되고 st_right에 append된다.

마지막에 st_left와 st_right을 extend를 통해 합쳐주는 과정을 거치게 된다.

이때, st_right는 append될 때 순서대로 쌓이게되므로 reversed를 이용하여 반대로 합쳐져야 한다.

1 2 3 4 5 6 /

의 리스트에서 L 1번이 이루어지면

1 2 3 4 5 / 6

L 1번이 다시 이루어지면

1 2 3 4 / 6 5

가 된다.

커서를 왼쪽으로 옮겼을 뿐, 순서가 바뀌면 안되므로 오른쪽 스택은 반대로 출력해야한다.

 

import sys
st_left = list(sys.stdin.readline().rstrip())
st_right = []

for _ in range(int(sys.stdin.readline())):
    command = list(sys.stdin.readline().split())

    if command[0] == 'L':
        if st_left:
            st_right.append(st_left.pop())
    elif command[0] == 'D':
        if st_right:
            st_left.append(st_right.pop())
    elif command[0] == 'B':
        if st_left:
            st_left.pop()
    else:
        st_left.append(command[1])

st_left.extend(reversed(st_right))
print(''.join(st_left))