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

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

1406번: 에디터

문제 설명

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

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

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

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

---

풀이과정

• 나의 풀이 

① 이 문제에서 직관적으로 파악한 것은 '어느 리스트에 문자를 저장하고 커서값을 지정한 후 커서값을 명령에 따라 이리저리 움직이며 명령을 수행해야겠군'이다.

② 아이디어 열기

 사실상 ①의 과정을 그대로 코드화하는 것은 크게 어렵지 않았다.

# 1406
import sys
input=sys.stdin.readline # input 대신 sys.stdin.readline 사용

word =list(input().strip()) # word에 편집기에 입력되는 문자열을 리스트화함. strip함수는 whitespace 없애는 용도
n = int(input())
c = len(word)         # 커서를 word의 길이로 초기화함

for i in range(n) :
    k = list(input().strip().split())    # 명령어를 받는 리스트
    if k[0] == 'P' :
        if c == len(word_lst) :
            word_lst.insert(c,k[1])
            c += 1
        else :
            word_lst.insert(c,k[1])
            c += 1
    elif k[0] == 'L' :
        if c == 0 :
            c = 0
        else  :
            c -= 1
    elif k[0] == 'D' :
        if c == len(word_lst) :
            c = len(word_lst)
        else  :
            c += 1
    elif k[0] == 'B' :
        if c == 0 :
            pass
        else :
            del word_lst[c-1]
            c -= 1

result = "".join(word_lst)  # "".joing(리스트) 로 리스트 안의 요소를 문자열로 출력
print(result)

 코드화한 후 엄청 쉬운 문제네~하고 제출하였지만 아니나 다를까... 시간초과의 늪에 빠져버렸다....

 어느 부분에서 시간초과를 초래하게 된 것인가? 그리고 다른 사람의 코드와 내 코드의 차이점이 대체 뭐길래 시간의 늪에 빠져버린걸까...에 대해 너무너무너무 궁금했다.

---

•  다른 이의 풀이

https://bnzn2426.tistory.com/112

 이분의 글을 보고 큰 해결점을 찾았다. 

 스택 한개에 대해 슬라이싱하거나 insert하는 것이 아닌 스택 두개를 이용해 스택을 합치는경우를 이용해 시간복잡도를 O(1)로 최소화하는 것이 관건이었다....!

 실제 코드는 다음과 같다.

from sys import stdin

stk1 = list(stdin.readline().strip())
stk2 = []
n = int(input())
for line in stdin :
    if line[0] == 'L' :
        if stk1 : stk2.append(stk1.pop())
        else : continue
    elif line[0] == 'D' :
        if stk2 : stk1.append(stk2.pop())
        else : continue
    elif line[0] == 'B' :
        if stk1 : stk1.pop()
        else : continue
    elif line[0] == 'P' :
        stk1.append(line[2])
print(''.join(stk1 + list(reversed(stk2))))

  굉장히 낯선 개념이기에... 빅오표기법과 시간복잡도에 대한 개념정리까지 고려해보았는데 분량이 너무 많을 것같아 따로 업로드하기로 하고 이번 게시물에서는 저 정답코드에 대한 이해를 목표로 하겠다.

(1) 첫줄 : 일단 input함수 대신 stdin함수를 사용한다.

(2) 두,세번째줄 : 두 개의 스택을 이용해 편집기의 문자열을 조정하자. 두 스택 사이 여백이 커서가 있는 부분이라 생각하면 L 명령이 들어온 경우 첫번째 스택의 마지막 항목을 두번째 스택에 추가한다. (물론 나중에 reverse해야겠지..?)

(3) for line in stdin 은 여러 줄의 입력을 받는 경우 사용하는 코드인듯하다...

---

후기

 파이썬이 정말 느린 언어구나라는 것을 실감하게 해주는 문제, 그리고 파이썬의 시간복잡도에 대한 공부의 필요성을 다시금 깨닫게 해주는 문제이다.