[자료구조/스택] 백준 1406 에디터 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1406번: 에디터

 

 

 

2. 문제 풀이

L: 커서를 왼쪽으로 한 칸 옮김
D: 커서를 오른쪽으로 한 칸 옮김
B: 커서 왼쪽에 있는 문자 삭제
P $: $ 문자를 커서 왼쪽에 추가

 에디터를 구현하는 문제입니다. 단순히 리스트 연산으로 구현가능하지만, 시간제한이 0.3초로 굉장히 짧습니다. 따라서 (연결)리스트의 삭제, 삽입 연산은 사용하면 안됩니다.

 

 

너무나도 높은 0.3초의 벽 (실버 3이 아닌데..)

 그대신, 커서를 기점으로 두 개의 스택으로 나누어서 담으면 해결할 수 있습니다. 

 

2022.02.10 - [Algorithm] - [Algorithm] 스택(stack), 차곡차곡 쌓는 자료구조

[Algorithm] 스택(stack), 차곡차곡 쌓는 자료구조

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
left_stack = list(input().rstrip())
right_stack = []

M = int(input())
for _ in range(M):
    command = input().rstrip()
    if command == 'L':
        # 왼쪽 스택이 비어있지 않다면, 1글자를 오른쪽 스택으로 옮김
        if left_stack:
            right_stack.append(left_stack.pop())

    elif command == 'D':
        # 오른쪽 스택이 비어있지 않다면, 1글자를 왼쪽 스택으로 옮김
        if right_stack:
            left_stack.append(right_stack.pop())

    elif command == 'B':
        # 왼쪽 스택 1글자 삭제
        if left_stack:
            left_stack.pop()

    else:
        # 왼쪽 스택 1글자 추가
        left_stack.append(command[-1])

# 문자열 합친 후 출력
left_stack.extend(reversed(right_stack))
print(''.join(left_stack))

 커서를 기점으로 오른쪽과 왼쪽 스택으로 나누어서 저장합니다.

 출력할 때에는 오른쪽 스택을 거꾸로 반전해서 합친 후, 출력합니다.