백준 1406번: 에디터 - Python 풀이

오늘의 문제

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

 

내 풀이

# 빠른 입력 (이거 쓰니까 시간초과 해결됨)
import sys
def input(): return sys.stdin.readline().rstrip()

S = input()
M = int(input())

# 커서의 왼쪽 문자열을 뜻하는 left_stack
left_stack = list(S) # 각 문자를 리스트의 요소로 저장
# 커서의 오른쪽 문자열을 뜻하는 right_stack
right_stack = []

# M만큼 반복
for _ in range(0, M):
    command = input().split() # P x 와 같은 형태를 처리하기 위해
    if command[0] == "L" and left_stack: # L 명령이고 left_stack이 비어있지 않다면
        last = left_stack.pop() # left_stack의 마지막 값을 pop
        right_stack.append(last) # 그 값을 right_stack의 맨 뒤로 push
    elif command[0] == "D" and right_stack: # D 명령이고 right_stack 비어있지 않다면
        last = right_stack.pop() # right_stack 마지막 값을 pop
        left_stack.append(last) # 그 값을 left_stack의 맨 뒤로 push
    elif command[0] == "B" and left_stack: # B 명령이고 left_stack이 비어있지 않다면
        left_stack.pop() # left_stack의 마지막 값을 pop
    elif command[0] == "P": # P 명령이면
        left_stack.append(command[1]) # 새 값을 left_stack의 맨 뒤로 push

right_stack.reverse() # right_stack에는 값들이 거꾸로 들어갔기 때문에 reverse 해줘야 올바른 방향이 됨
answer = left_stack + right_stack # 커서의 왼쪽 값과 오른쪽 값을 합친 리스트 answer

print("".join(answer)) # 리스트 answer를 공백없이 문자열로 합친 후 출력

 

핵심은 스택 2개를 사용하여 푸는 문제.

커서의 왼쪽에 있는 값들과 오른쪽의 있는 값들을 각각 스택을 통해 관리한다.

 

커서의 왼쪽에 있다가 오른쪽으로 가게 되는 문자들은 left_stack에서 right_stack의 방향으로 이동하는데, 이때 스택의 특성상 left_stack의 맨 뒤 값이 right_stack의 맨 뒤로 쌓이게 된다. 문자가 커서의 오른쪽에 있다가 왼쪽으로 이동할 때에도 맨 뒤에 있는 값들끼리 바꾸면 돼서 이 편리함 때문에 '스택'을 사용하는 것이다.

 

그래서 이렇게 되면 left_stack과 달리 right_stack에는 커서 오른쪽의 문자들이 거꾸로 배치되는데, 이는 명령을 다 수행한 후(for문 종료 이후) 리스트를 reverse 하면 된다.

 

-> 여기까지 구현했는데 계속 시간초과가 떠서 질문 게시판을 보니, sys 라이브러리를 써서 입력 시간을 줄이라고 했다.

import sys
def input(): return sys.stdin.readline().rstrip()

 

그랬더니 통과핑~