[백준/1406/파이썬] 에디터

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

1406번: 에디터

조건

• 영어 소문자가 input으로 옴. 최대 60,000글자
• 'Cusor'가 있는데, 커서는 문장의 맨앞, 맨뒤 또는 문장의 임이의 곳에 위치할 수 있음.
• 길이가 L인 문자열이 편집기에 있으면, L+1가지 경우가 있음.

이 편집기가 지원하는 명령어

• L: 커서를 왼쪽으로 한 칸 옮김.( 커서가 맨 앞이면, 무시)
• D:커서를 오른쪽으로 한 칸 옮김.(커서가 맨 뒤면 , 무시)
• B 커서 왼쪽에 있는 문자를 삭제함.(커서가 맨앞이면 무시)
• P$:$라는 문자를 커서의 왼쪽에 추가함.

입력

• 첫째 줄에는 문자열이 주어진다. 길이가 N이다. (1≤N≤100,000)
• 둘째 줄에는 입력할 명령의 개수 M이 온다. (1≤M≤500,000)
• TimeLimit:0.3s

 

 

SOL)

완전탐색

TimeLimit가 이럭게 작지않다면, 배열의 크기를 2L+1만큼 만들어서, 사이사이의 공백을 직접 구현하는? 아주 쉽고 직관적인 방법을 택했겠지만, 문자열의 크기가 N=100,000이기 때문에, 공백칸 만큼 시간을 만들어 준다고해도, 탐색을 할때마다, N이 걸리기 때문에,0.3초는 더 넘게 걸릴거임.

 

1. 연결리스트를 떠올림.

사실, 삽입/삭제가 일어나고, 커서 (포인터)가 있으니까 연결리스트가 딱 떠오르는데, Python으로 어떻게 구현하는지 모름. 파이썬에 포인터 기능이 없음..(이 문제를 풀 당시에는 못떠올림. 없다고 생각함)

 

이런 느낌으로, A,B,C를 하나하나 연결리스트에 넣어주고, 저 연결되는 부분을 공백으로 생각하면 되지않을까? 라고 생각함. 

 

이걸 에디터의 동작에 맞게 해석하면 이렇게 할 수 있음.

L :커서 왼쪽으로 움직이라는 거면, Node의 Head 쪽에 가면되는거고,

D:커서의 오른쪽 움직이는 거면, Node의 tail쪽에 가면 되고

B:커서를 헤드로 옮기고, 헤드에 들어있는 주소값에 해당하는 노드를 지워버리면 됨.

노드 지우고, 다시 앞의 노드와 연결 시켜주면 됨.

P$: 새로운 노드를 만들어서, 연결시켜주면 됨.

 

2. 연결리스트를 사용하지 않고, 풀 수 있을까? ..몰겠음 ⇒멘토님에게 질문드림!

 

멘토님

• Python에는 연결리스트를 구현하기 힘드니, 다른 자료구조를 이용해서 푸는게 더 낫다고 생각한다.
• 커서 기준으로 왼쪽을 저장할 자료구조 하나, 오른쪽을 저장할 자료구조 하나를 두는 방법이 있다.

처음에는 안와닿았지만, 그림을 그려보니 느낌이 왔다.

 

• stack을 양쪽으로 두고 쓰면, Cusor 처럼, 배열의 중간중간을 내가 컨트롤 할 수 있다.

바로 코드 작성에 들어갔다.

import sys 
input=sys.stdin.readline
stk_left=list(input().strip()) #초기상태 만들어주기.
size=len(stk_left)
stk_right=[]
cusor = len(stk_left)

n=int(input())

for i in range(n):
	cmd= input().strip()
	if cmd[0] == "P":
		stk_left.append(cmd[2]) # P공백K 니까, cmd 2인가?  
	elif cmd[0] == "L" and stk_left !=[]: 
		stk_right.append(stk_left.pop())
		cusor -=1
	elif cmd[0] == "D" and stk_right !=[] :
		stk_left.append(stk_right.pop())
		cusor +=1
	elif cmd[0] == "B"and stk_left !=[]:
		stk_left.pop()
print("".join(stk_left+list(reversed(stk_right))))

• 틀렸던이유

input 부분에서, P K 이런식으로 오면, cmd[0]부분을 체크해줘야하는데, cmd =="P" 이런식으로 처리해줌. 디테일 챙기자.