[Python] 백준 1406번: 에디터

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

1406번: 에디터

import sys
input = sys.stdin.readline

left = list(input().rstrip())
right = []

M = int(input())

for _ in range(M):
    curLine = list(map(str, input().rstrip().split()))

    if curLine[0] == 'L' and left:
        right.append(left.pop())
    elif curLine[0] == 'D' and right:
        left.append(right.pop())
    elif curLine[0] == 'B' and left:
        left.pop()
    elif curLine[0] == 'P':
        left.append(curLine[1])

print("".join(left)+"".join(reversed(right)))

 

해당 문제에서 입력받는 문자열 및 명령의 개수가 매우 커서, 단순하게 커서의 위치를 변경해가면서 리스트에 인덱싱을 통해 접근하게 되면 시간 초과로 풀리지 않는다.

따라서 우리는 '스택'을 이용한다. 왜냐하면, 커서는 커서와 인접한 문자들만 신경써주면 되기 때문이다.

ab|cd라고 했을 때의 스택의 모형이다.

1. 커서를 왼쪽으로 옮겨야할 경우(a|bcd), left의 b를 pop하여 그것을 right에 전달한다.

2. 커서를 오른쪽으로 옮겨야할 경우(abc|d), right의 c를 pop하여 그것을 left에 전달한다.

3. 백스페이스를 누를 경우(a|cd), left의 b를 pop한다.

4. 'z'라는 문자를 입력할 경우(abz|cd), left에 'r'을 push한다.