문제

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

문제 설명

그냥 보면 리스트를 사용하여 구현해야 할 것 같지만, 리스트 하나를 사용해 구현하면 시간제한조건에 걸린다.
따라서, 리스트 두개를 사용해 스택으로 사용해야 시간제한조건 안에 동작을 할 수 있다.

L

• 리스트 : 커서를 왼쪽으로 한칸 옮긴다. O(1)
• 스택 : 리스트에서는 인덱스를 -1 하면 되지만, 스택으로 구현한다면, 왼쪽 스택에서 pop()하여 원소를 꺼내 오른쪽 스택에 append() 한다. O(1)

D

• 리스트 : 커서를 오른쪽으로 한칸 옮긴다. O(1)
• 스택 : 스택으로 구현할 때는, 오른쪽 스택에서 pop()하여 왼쪽 스택에 넣는다. O(1)

B

• 리스트 : 커서 왼쪽의 문자를 하나 제거한다. O(N)
• 스택 : 스택으로 구현시 왼쪽 스택에서 pop()한다. O(1)

P $

• 리스트 : 커서 왼쪽의 문자를 하나 추가한다. O(N)
• 스택 : 스택으로 구현시 왼쪽 스택에서 append()한다. O(1)

코드

import sys
input = sys.stdin.readline

# 리스트 하나를 사용하면 시간제한안에 수행하지 못함
# 스택 두개를 이용한다. 커서는 두개의 스택 그 가운데를 가리킨다고 생각하자. 
left = list(input().strip())
right = []

for i in range(int(input().strip())):
    order = input().strip()
    if order[0] == 'L':
        if left:
            right.append(left.pop())

    elif order[0] == 'D':
        if right:
            left.append(right.pop())

    elif order[0] == 'B':
        if left:
            left.pop()

    elif order[0] == 'P':
        left.append(order[-1])

while right:
    left.append(right.pop())
print(''.join(left))