[83일차][백준][자료구조, 구현, 문자열][1406]에디터

문제 설명

한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.

이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.

이 편집기가 지원하는 명령어는 다음과 같다.

L	커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
D	커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
B	커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨) 삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임
P $	$라는 문자를 커서 왼쪽에 추가함

 

초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.

 

입력

첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 M(1 ≤ M ≤ 500,000)이 주어진다. 셋째 줄부터 M개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 명령어는 위의 네 가지 중 하나의 형태로만 주어진다.

 

출력

첫째 줄에 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 출력한다.

 

예제 입력, 예제 출력

abcd 3 P x L P y	abcdyx
abc 9 L L L L L P x L B P y	yxabc
dmih 11 B B P x L B B B P y D D P z	yxz

 

 

코드 및 설명

import sys

n_str = list(sys.stdin.readline().strip())
m = int(sys.stdin.readline())
cursor = len(n_str)

for i in range(m):
  cli = sys.stdin.readline().strip().split(" ")
  cli_len = len(cli)
   
  if cli[0] == 'L' or cli[0] == 'B': 
    if cursor != 0:      
      if cli[0] == 'B':
        del n_str[cursor]    
      cursor -= 1      
  else:
    if cli[0] == 'P':
      n_str.insert(cursor, cli[1])
      cursor += 1
    else:
      if cursor != len(n_str):
        cursor += 1         
  
print("".join(n_str))

 

처음 이 문제를 풀 때 아 이거 그냥 커서 움직 체크해서 빼주고 넣어주고 하면 되겠네라고 쉽게 생각하면서 풀었는 데...

 

시간까지 고려했어야 했다... 시간복잡도를 생각하고 풀어야 한다.

 

그래서 스택으로 풀어보았다.

 

import sys

left_stack = list(sys.stdin.readline().strip())
m = int(sys.stdin.readline())
right_stack = []

for i in range(m):
  cli = sys.stdin.readline().strip().split(" ")

  if cli[0] == 'L':    
    if left_stack != []:
      left = left_stack.pop()
      right_stack.append(left)

  if cli[0] == 'D':
    if right_stack != []:
      right = right_stack.pop()
      left_stack.append(right)

  if cli[0] == 'B':
    if left_stack:
      left_stack.pop()
    
  if cli[0] == 'P':
    left_stack.append(cli[1])
   
print("".join(left_stack)+"".join( right_stack[j] for j in range(len(right_stack)-1, -1, -1)))

 

문자열 받을 때 left_stack 변수에 담는다. 처음 커서에 시작은 문자열 마지막이기때문에 left에 담는다고 보면 된다.

 

L 일때는 왼쪽으로 커서가 이동해야하기 때문에 left_stack에서 pop을 하여 뽑아낸 값을 right_stack에 넣어준다.

 

D 일때는 오른쪽으로 커서가 이동해야하기 때문에 right_stack에서 pop을 하여 뽑아낸 값을 left_stack에 넣어준다.

 

B 일때는 왼쪽에 있는 값을 삭제해야하기 때문에 left_stack에서 pop을 한다.

 

위 3개에서 유의해야할 점은 left_stack이 비어있거나, right_stack이 비어있는 지 체크를 해줘야한다는 점!!!

 

P 일때는 왼쪽에 값을 추가하는 것이기 때문에 left_stack에 append()를 진행해준다.

 

정답은 left_stack과 right_stack의 값을 합쳐서 프린트해주면 된다.