[백준알고리즘] 1406번: 에디터 -Python

[백준알고리즘] 1406번: 에디터 -Python

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

1406번: 에디터

이번 문제는 시간 제한이 매우 짧다. 무시하고 리스트와 현재 커서의 위치를 포인팅 하는 변수를 이용해서 리스트의 append와 pop을 이용했었다. 시간 초과가 뜨고 찾아보니 리스트의 슬라이싱은 O(N)이라고 한다. 당연히 pop, append 등이 자유로워 더블 링크드 리스트같은 존재일 줄 알았다...ㅎㅎ..  그러고보니 덱을 사용하면 덱은 더블 링크드 리스트일 것 같다. 리스트는 remove 등도 어차피 순차 탐색할 것이기 때문에 단순하게 만들었나 보다.

 

아무튼 이 문제를 해결하기 위해서 한참 생각하다 딴짓하다 하다가 스택을 두 개 이용해 보기로 했다. 파이썬은 리스트를 스택으로 사용할 수 있기 때문에 리스트를 사용했다. 통과할 것 같았는데 시간이 되게 빠듯하길래 일단 시도해 보자 하고 했는데 다들 스택 두 개나 덱 두 개를 이용해서 풀었다.

 

처음 입력을 한쪽에 모두 담아두고 커서는 항상 left_stack의 가장 위의 값이라고 생각을 했다.

 

따라서 L이 나오게 되면, 왼쪽 값의 하나를 pop 시키고, 오른쪽에 추가해주었다. D는 반대로 해주었다.

B일 경우에는 왼쪽에서 하나를 pop 시키기만 했고, P일 경우에는 왼쪽에 추가를 해주었다.

 

right_stack의 경우에는 마지막에 뒤에서부터 읽기 위해서 [::-1]을 해주었다. [::-1]을 하게되면 리스트가 뒤집힌다.

import sys

left_stack = list(sys.stdin.readline()[:-1])
right_stack = list()
testcase = int(sys.stdin.readline())

for _ in range(testcase):
    cmd = sys.stdin.readline()
    if cmd[0] == 'L' and left_stack:
        right_stack.append(left_stack.pop())
    elif cmd[0] == 'D' and right_stack:
        left_stack.append(right_stack.pop())
    elif cmd[0] == 'B' and left_stack:
        left_stack.pop()
    elif cmd[0] == 'P':
        left_stack.append(cmd[2])

sys.stdout.write(''.join(left_stack + right_stack[::-1]))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다