[백준/Python] 1406번: 에디터

📖  문제 링크

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

1406번: 에디터

 

👩‍💻  문제풀이

 

파이썬 리스트 명령어의 시간 복잡도에 대해 정확히 공부하지 못해서,  먼저 리스트를 사용해 구조만을 파악해보고자 했다.

 

cursor라는 변수에 명령어의 조건에 따라 값을 더하고 빼주었고,

입력과 삽입, 지우기 모두 cursor의 인덱스에 따라 진행하였다. 

 

코드는 아래와 같다. 

 

#<시간초과 코드>
import sys

word = list(sys.stdin.readline().rstrip('\n'))
n = int(input())

cursor = len(word)

for i in range(n):
    command = sys.stdin.readline().split()   
    if command[0] == 'L':
        if cursor == 0:
            continue
        else:
            cursor -= 1
    elif command[0] == 'D':
        if cursor == len(word):
            continue
        else:
            cursor += 1
    elif command[0] == 'B':
        if cursor == 0:
            continue
        else:
            del word[cursor-1]
            cursor -= 1
    elif command[0] == 'P':
        word.insert(cursor, command[1])
        cursor += 1
        
for i in word:
    print(i, end='')

 

 

당연하게도 시간초과! 

 

 

여러 블로그를 탐구해보니, 아래의 블로그에 자료형 별 시간 복잡도 설명이 자세히 나와있었다. 

 

https://wayhome25.github.io/python/2017/06/14/time-complexity/ 

파이썬 자료형 별 주요 연산자의 시간 복잡도 (Big-O) · 초보몽키의 개발공부로그

 

 

내가 사용한 insert, del함수의 경우 시간복잡도가 O(N)으로 append, pop에 비해 매우 느린 것을 볼 수 있다. 

 

 

그래서 append와 pop만을 사용해서 다시 시도해보았다. 

append는 리스트의 가장 마지막에 요소가 추가되므로, 문제의 조건을 충족하기위해 stack을 두개 사용해야 한다.

이런 식으로 스택과 스택 사이의 빈 공간이 커서라고 가정하는 것이다. 

 

 

여기서 주의할 점!! 

append와 pop의 특성을 고려했을 때,

오른쪽 스택은 가장 마지막에 요소가 추가되고 삭제될 수밖에 없으므로 요소의 순서가 거꾸로 배치된다. 

이해가 쉽도록 예제 2를 단계마다 출력해보았다.

 

 

 

따라서, 마지막에 결과를 출력할 때 오른쪽 스택을 거꾸로 출력해줘야 정확한 결과를 얻을 수 있다.

 

 

이때, reverse함수가 아니라 reversed 함수를 사용해야 하는데, 

그 이유는 reverse함수가 스택이 비어있을 경우 오류를 출력하기 때문이다.

 

 

또한 reversed 함수는 list함수가 아니라 내장 함수이기 때문에

list(reversed(stack_right))의 형태로 사용해야 한다. ([::-1]의 형태로 출력해도 무방하다)

 

 

✅  최종 코드

 

import sys

stack_left = list(sys.stdin.readline().rstrip('\n'))
stack_right = []
print(stack_left, stack_right)
n = int(input())
cursor = len(stack_left)

for i in range(n):
    command = sys.stdin.readline().split()   
    if command[0] == 'L':
        if stack_left:
            stack_right.append(stack_left.pop())
            print(stack_left, stack_right)
    elif command[0] == 'D':
        if stack_right:
            stack_left.append(stack_right.pop())
            print(stack_left, stack_right)
    elif command[0] == 'B':
        if stack_left:
            stack_left.pop()
            print(stack_left, stack_right)
    elif command[0] == 'P':
        stack_left.append(command[1])
        print(stack_left, stack_right)
        
#print(''.join(stack_left + list(reversed(stack_right))))
print("".join(stack_left) + "".join(stack_right[::-1]))

 

 

굉장히 배울 점이 많은 문제였다. 

시간 복잡도와 자료구조에 대한 이해가 부족함을 느낀다. 

꾸준히 공부하자 : )