백준 1406(파이썬/python)

문제

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

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

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

'L' 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)

'D' 커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)

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

'P $' $라는 문자를 커서 왼쪽에 추가함

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

 

입력

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

 

출력

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

 

코드

from sys import stdin
lis = list(stdin.readline().strip())
n = int(stdin.readline())
cursur = len(lis)
for _ in range(n):
    inp = stdin.readline().strip()
    if inp[0] == 'L':
        if cursur > 0:
            cursur -= 1
    elif inp[0] == 'D':
        if cursur < len(lis):
            cursur += 1
    elif inp[0] == 'B':
        if cursur != 0:
            del lis[cursur-1]
            cursur -= 1
    else:
        lis.insert(cursur, inp[2])
        cursur += 1
print(''.join(lis))

 

 

실패

한참을 코딩한 끝에 맞는 결과가 나오는 프로그램을 완성했다. 하지만 이게 웬걸 제출해보니 시간 초과라는 차가운 네글자만 나를 반길 뿐이었다. 그리도 또 한참 실행시간을 줄이기 위해 코딩을 하였지만 시간을 초과했다는 단호한 네글자만 나를 반길 뿐이었다. 

그래서 어쩔 수 없이 최후의 수단으로 다른 사람들은 어떻게 했는지 찾아보게 되었다.

import sys

st1 = list(sys.stdin.readline().rstrip())
st2 = []
for _ in range(int(sys.stdin.readline())):
	command = list(sys.stdin.readline().split())
    if command[0] == 'L':
		if st1:
        	st2.append(st1.pop())
	elif command[0] == 'D':
    	if st2:
        	st1.append(st2.pop())

	elif command[0] == 'B':
    	if st1:
        	st1.pop()
	else:
    	st1.append(command[1])
st1.extend(reversed(st2))
print(''.join(st1))

다른사람들이 한걸 보니 이런 엄청난 방법이 있었구나 신기하고 흥미로워하는 감정과 애초에 내가 시간을 얼마나 들이던 풀지 못할 문제였구나 하는 허무함이 동시에 밀려왔다.

이 방법은 기존에 스택 하나만 사용해서 문제를 해결하려 했던 나의 고정된 생각을 깨고 스택 두개를 활용하여 하나는 커서 앞쪽을 다른 하나는 커서 뒤쪽을 저장하여 pop과 append만으로 커서의 이동을 표현해 실행시간을 획기적으로 줄인 뒤 모든 명령을 시행하고 두 스택을 합쳐서 출력하는 방식이었다.

오늘 내 코딩 지식이 얼마나 얕은지 확인하면서 더 열심히 해야겠다는 생각이 드는 하루였다.