[Python 3] BOJ - 1406 "에디터"

 # 문제 링크 : https://www.acmicpc.net/problem/1406

1406번: 에디터

 # 풀이 :

 개인적으로 이 문제는 커서의 위치를 굳이 구하지 않아도 된다는 점과 스택을 이용해야 한다. 문제의 시간제한이 0.3초로 상당히 짧기 때문에 실제 커서의 위치를 구하고 문자의 삽입이나 삭제 쿼리가 들어오는 경우 그것을 실제로 처리하려면 시간 초과를 피할 수 없기 때문이다. 

 그런데 커서를 기준으로 삭제와 삽입은 항상 왼쪽으로 일어나고, 오른쪽에는 아무것도 일어나지 않는다. 따라서 왼쪽 스택과 오른쪽 스택을 두어 쿼리에 따라 처리해주면 된다.

<그림 1. abc인 경우>

 그림1은 문제의 테스트 케이스 2번을 나타낸 것이다. 처음에는 항상 문자열의 맨 뒤에 커서가 위치하므로 모든 문자열이 왼쪽 스택에 들어간다.

<그림 2. 첫번째 쿼리 처리>

 커서를 왼쪽으로 움직이므로 ab만 커서를 기준으로 왼쪽에 있고 c는 커서를 기준으로 오른쪽에 있다. 따라서, 가장 왼쪽 스택에 pop한 원소를 오른쪽 스택에 넣는다

<그림 3. 두번째 쿼리 처리>

커서를 다시 왼쪽으로 옮겼으므로 커서를 기준으로 a만 왼쪽 스택에 있으므로 그림 2의 과정을 반복한다

<그림 4. 세번째 쿼리 처리>

  그림4는 세번째 쿼리를 옮긴 이후의 상황이다. 만약 쿼리가 여기서 끝나고 오른쪽 스택이 남았다면 오른쪽 스택은 순서를 거꾸로 뒤집어 출력해야 올바른 문자열을 구할 수 있다. 네번째 쿼리와 다섯번째 쿼리 모두 현재 커서가 제일 왼쪽인데 L이므로(커서를 왼쪽으로 옮기는 쿼리) 왼쪽 스택과 오른쪽 스택에는 아무것도 일어나지 않는다.

<그림 5. 여섯번째 쿼리 처리>

 그림 5에서는 x를 삽입하는 쿼리를 나타낸다. 문제에서 문자를 삽입할 때는 커서의 왼쪽에 삽입한다고 했으므로 왼쪽 스택에 x를 추가한다

<그림 6. 일곱번째 쿼리 처리>

  커서를 왼쪽으로 옮겼으므로 기존의 처리 방식과 같이 왼쪽 스택의 pop한 원소를 오른쪽 스택에 넣는다

<그림 7. 여덟번째 쿼리 처리>

 여덟번째 쿼리로 삭제 쿼리가 들어왔다. 문제에서 삭제 쿼리는 커서를 기준으로 왼쪽의 문자를 삭제하는 것으므로 만일 왼쪽 스택이 비어있지 않았다면 왼쪽 스택에서 pop을 시켜주면 된다. 그러나, 그림 7과 같이 왼쪽 스택이 비어있는데 pop을 하면 런타임 에러가 발생하므로 반드시 삭제는 왼쪽 스택이 있는 경우만 해주어야 한다

<그림 8. 아홉번째 쿼리 처리>

 그림 8은 마지막 쿼리까지 끝낸 후 최종적인 왼쪽 스택, 오른쪽 스택의 상황이다. 왼쪽 스택과 오른쪽 스택은 실제 커서의 왼쪽 문자와 오른쪽 문자들을 올바르게 각각 담고 있는 것을 알 수 있다. 따라서, 전체 문자열을 출력하려면 왼쪽 스택은 그대로 출력하면서 오른쪽 스택은 뒤집고 왼쪽 스택에 더해주면 정답을 올바르게 시간안에 구할 수 있다

 

 # 코드

import sys

# 입력부
n = sys.stdin.readline().rstrip()
b = int(sys.stdin.readline())

# l_stack : 왼쪽 스택(문자열로 초기화)
# r_stack : 오른쪽 스택
l_stack = list(n)
r_stack = []

for s in range(b):
    # x : 쿼리
    x = sys.stdin.readline().rstrip()
    # 만일 왼쪽으로 이동 시 왼쪽에서 오른쪽으로 옮김
    if x == "L" and l_stack:
        r_stack.append(l_stack.pop())
    # 만일 오른쪽으로 이동 시 오른쪽에서 왼쪽으로 옮김
    elif x == "D" and r_stack:
        l_stack.append(r_stack.pop())
    # 만일 삭제 시 왼쪽에서 하나 삭제
    elif x == "B" and l_stack:
        l_stack.pop()
    # 만일 삽입 시 왼쪽에 문자 삽입
    else:
        if x[0] == "P":
            l_stack.append(x[2])

# 오른쪽 스택을 뒤집어서 왼쪽 스택과 합친 후 출력
print(''.join(l_stack + r_stack[::-1]))