[백준] 1406번 에디터 - 파이썬(Python)

시간 제한	메모리 제한
0.3 초	512 MB

문제

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

1406번: 에디터

 

나의 풀이

string_list = list(input())
cursor = len(string_list)

for _ in range(int(input())):
    command = list(input().split())
    if command[0] == 'P':
        string_list.insert(cursor, command[1])
        cursor += 1
  
    elif command[0] == 'L':
        if cursor > 0:
            cursor -= 1

    elif command[0] =='D':
        if cursor < len(string_list):
            cursor += 1
  
    else:
        if cursor > 0:
            string_list.remove(string_list[cursor-1])

print(''.join(string_list))

 

접근 방법 및 코드 설명

 

커서를 어떤 식으로 표현해줘야할지 고민이 많았다.

 

 입력값으로 P나 B가 들어왔을 때 처리해줘야 할 값들은 커서의 왼쪽 값이기 때문에, 커서를 string의 길이로 잡아줬다.

 

문제를 풀면서 값을 추가할 때는 insert를, 제거할 때는 remove를 사용하는 것 외에는 다른 방법이 생각나지 않아 일단 그 방법을 이용하기로 했다.

 

문제 풀며 찾아보며 안 사실인데, insert의 경우 삽입위치에 대한 파라미터로 리스트 길이 이상의 값을 넣어주면 맨 뒤에 값이 추가된다.

 

my_list = ['a', 'b', 'c']

my_list.insert(5, 'x')
print(my_list)

 

커서를 움직이는 명령의 경우, 커서의 범위가 0보다 작아지지 않고 리스트의 길이보다 길어지지 않는 범위 내에서 움직일 수 있도록 해줬다.

 

삭제의 경우, cursor로 지정된 값에서 1을 뺀 값을 리스트의 인덱스로 넣어 처리해줬다.

 

제출 전 테스트로 돌려본 결과 올바른 값을 출력했지만, 아쉽게도 시간초과 판정이 났다.

 

 

실제로 해당 문제는 시간초과가 0.3초로 일반적인 문제보다 훨씬 짧은 시간제한을 가지고 있다.

 

문제에 언급되었듯, 입력가능한 명령의 수는 최대 500000개로 매우 많기 때문에, O(n)만큼의 시간을 소요하는 insert와 remove 함수를 사용할 경우, 최악의 경우에 문자열의 최대 길이인 100000에 최대 명령 수 500000을 곱한 숫자만큼의 연산을 진행해야한다.

 

 

다른 사람의 풀이

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))

정말 감탄할만한 접근방법이 아닐 수 없었다.

 

아직 스스로가 자료구조 활용에 많이 약하다는 것을 절실하게 느낀 풀이법이었다.

 

위 코드의 접근법은, 커서를 기준으로 문자열을 스택 두개에 나누어 담겠다는 것이다.

 

 

이렇게하면, 값을 추가하거나 삭제하는 연산, 커서를 이동하는 연산 모두 append와 pop을 통해 할 수 있어 O(1) 시간의 연산을 보장한다.

 

반복문에서 명령을 모두 수행한 후, stack2를 뒤집어준 후 extend 함수를 활용해 두 stack을 합쳐주었다.

 

출력은 문자열로 해야하기 때문에 join함수를 활용했다.

 

 

* 주의

 

마지막에 stack2를 뒤집어주는 과정에서 반드시 st2.reverse() 가 아닌 reversed(st2) 를 사용해줘야한다.

 

만약 모든 명령이 끝난 후 st2에 값이 아무것도 존재하지 않는다면 st2.reverse() 는 TypeError를 띄우기 때문이다.

 

반면에 reversed(st2) 는 st2에 값이 존재하지 않더라도 오류를 띄우지 않고 우리가 생각한대로 잘 작동한다.