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

문제를 풀었지만 정말 복잡하게 풀었다... 그리고 메모리 초과가 나서 코드를 살펴보니 del의 경우 O(N)이기 떄문에 for 문과 함께 전체적으로 O(N^2) 이기 때문에 효율적이지 못한 코드이다. 요새 코딩테스트를 보면서 메모리 효율적으로 사용해야하는 코드가 필요하다는 것을 절실히 느낀다.

import sys
s = list(sys.stdin.readline())
n = int(sys.stdin.readline())
c_idx = len(s)
for _ in range(n):
    input_ = list(map(str, sys.stdin.readline().split()))
    if input_[0] == "L": # 왼쪽
        if c_idx == 0: # 커서가 맨 왼쪽에 있다면
            continue
        c_idx -= 1 # 왼쪽으로 커서 이동
    elif input_[0] == "D": # 오른쪽
        if c_idx == len(s): # 맨 왼쪽
            continue
        c_idx += 1 # 오른쪽으로 커서 이동
    elif input_[0] == "B": # 왼쪽에 있는 문자 삭제
        if c_idx == 0: # 맨 왼쪽이면 무시
            continue
        c_idx -= 1 # 왼쪽으로 커서 이동
        del s[c_idx] # 삭제
    elif input_[0] == "P": # 문자를 커서 왼쪽에 추가
        if c_idx == len(s):  # 맨 마지막
            s.extend(input_[1]) # 뒤에 추가
        elif c_idx == 0: # 맨 앞에
            tmp = s[c_idx:]
            s[c_idx] = input_[1]
            s = [s[0]] + tmp
        else: # 중간
            tmp = s[c_idx:]
            s[c_idx] = input_[1]
            s.extend(tmp)
        c_idx += 1
print("".join(s))

 

 

다른 사람 풀이를 참고했는데 스택 자료구조를 사용하여 기가막히게 이 문제를 풀었다. 스택을 통해 삭제, 추가를 O(1)로 해결을 해서 전체적으로 O(N)의 시간 복잡도를 나오게 하였다.

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

 

처음에 제공해주는 문자 리스트 S, 스택을 T라고 가정해보자.

1. L: 왼쪽으로 갈때 커서의 오른쪽에 있는 문자를 T에 넣는다.

2. D: 오른쪽으로 갈때 T에 있는 것을 pop하여 S에 넣는다.

3. Push x: S에 append로 추가한다.

4. B: S를 pop한다.

 

이렇게 스택을 사용하여 메모리, 시간 효율성을 챙길 수 있다는 것을 배웠다.