백준 #1406 - [S2] 에디터 : 스택

(python3)

1406번: 에디터

 

커서 기준 좌우로 나눠서 스택을 활용하기

배열의 중간에 값을 추가하거나 삭제하는건 굉장히 고된 일입니다. 이 문제의 경우 가운데 값을 고치게 되면 시간초과가 발생합니다.

커서 기준으로 배열을 나눠서 관리하면 두 배열의 맨 뒤 값만 고치면 됩니다. 이 경우 배열로 풀려면 커서 오른쪽 문자열 배열은 순서를 거꾸로 관리해야합니다. 왼쪽끝에서 떼어낸건 오른쪽 맨 앞에 붙어야하기 때문이죠.

저는 이것까지 고려하지않고 직관적으로 작성하기 위해서 collections 의 deque 을 사용해주었습니다. 덱을 사용하면 앞뒤의 수정이 O(1) 에 가능합니다.

 

+= 과 join 의 속도 차이

마지막 출력에 덱의 내용을 하나의 string 으로 출력하기 위해서 for 문에 += 으로 하나하나 붙여주었더니 시간초과가 발생했습니다. join 을 사용하니 통과됩니다.

join 으로 붙이는게 for 문을 돌리는것보다 4배 빠르다고 하네요. += 구문이 매번 class 에 대한 새로운 representation 을 생성하기 때문이라고 합니다.

파이썬에 대한 이해도가 깊지 않아서.. 일단 단순하게 말하면 하나씩 가져다 붙이면서 매번 새로운 메모리를 할당하는것보다 두개를 통째로 갖다 붙이는게 효율적이다.. 정도로 이해했습니다. 다음엔 join 의 내부구현을 좀 더 알아봐야할것같습니다.

 

코드

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

import sys
from collections import deque
def solution(input) :
    # 커서 기준 좌우 갈라서 덱 활용
    def command_in(com) :
        if com[0] == 'L' :
            if len(DL) :
                DR.appendleft(DL.pop())

        elif com[0] == 'D' :
            if len(DR) :
                DL.append(DR.popleft())

        elif com[0] == 'B' :
            if len(DL) :
                DL.pop()
            
        elif com[0] == 'P' :
            DL.append(com[2])

    DL = deque(input().strip())
    DR = deque()

    M = int(input().strip())
    for _ in range(M) :
        command_in(input().strip())
    
    # T = DL+DR
    # ans = ''
    # for i in T : ans+=i # 시간초과
    # print(ans)
    
    print(''.join(DL+DR))

input = sys.stdin.readline
solution(input)

 

my solved.ac :

solved.ac