[BOJ 1406] 에디터 - 파이썬 풀이

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

1406번: 에디터

꽤나 간단한 문제입니다.

리스트(list)로 풀 경우 시간초과가 뜨는데, 파이썬의 리스트 시간복잡도를 보면

list.pop(0), list.index, list.insert, list.count, x in list, list[:-1] 등은 다 O(N)입니다.

리스트는 배열로 표현됩니다. 그렇기 때문에 배열의 크기가 증가하거나 index 값이 작은 부분에 삽입 또는 삭제가 일어날 경우 비효율적입니다. 이럴 경우에는 collections.deque를 사용하는게 보다 효율적입니다.

 

따라서 덱(Deque : Double Ended Queue)을 이용하여 풀었습니다.

덱(Deque)의 가장 큰 특징은 양쪽에서 모두 입출력이 가능하다는 것입니다.

 

deque는 내부적으로 doubly linked list로 표현됩니다. 양 끝단에 모두 접근이 가능합니다. 단, deque의 가운데 부분을 찾거나, 중간에 삽입, 제거하는 것은 더 느립니다.

import sys
from collections import deque
class Editor:
    def __init__(self, input_text):
        self.left_deque = deque(input_text)
        self.right_deque = deque()

    # 커서를 왼쪽으로 한칸 옮김
    def move_cursor_left(self):
        if self.left_deque:
            self.right_deque.appendleft(self.left_deque.pop())

    # 커서를 오른쪽으로 한칸 옮김
    def move_cursor_right(self):
        if self.right_deque:
            self.left_deque.append(self.right_deque.popleft())

    # 커서 왼쪽에 있는 문자를 삭제함
    def delete_left_character(self):
        if self.left_deque:
            self.left_deque.pop()

    # 문자를 커서 왼쪽에 추가함
    def add_character_to_left(self, character2add):
        self.left_deque.append(character2add)


editor = Editor(sys.stdin.readline().strip())

N = int(sys.stdin.readline().strip())
while N:
    command = sys.stdin.readline().strip()
    if command[0] == 'L':
        editor.move_cursor_left()
    elif command[0] == 'D':
        editor.move_cursor_right()
    elif command[0] == 'B':
        editor.delete_left_character()
    else:
        editor.add_character_to_left(command[2])
    N -= 1

print(''.join(editor.left_deque) + ''.join(editor.right_deque))