1406 에디터 (Python)

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

 

import sys
input = sys.stdin.readline

class Node():
    def __init__(self,s,p,n):
        self.string = s
        self.prev = p
        self.next = n

    def delete(self):
        if self.prev:
            self.prev.next = self.next
        if self.next:
            self.next.prev = self.prev

    def addLeft(self,s):
        new_node = Node(s,self.prev,self)
        if self.prev:
            self.prev.next = new_node
        self.prev = new_node

init_str = input().strip()
M = int(input())
prev = None
for s in init_str:
    node = Node(s, prev, None) # 새 노드 만들고
    if prev:
        prev.next = node # 이전 노드에 연결
    prev = node # 이전 노드를 이번 노드로 만들기

# 커서를 노드 왼쪽에 두기 위해 마지막 배열 추가.
endNode = Node(None,node,None)
node.next = endNode
node = endNode

# 커서는 노드의 왼쪽에 있는 것으로 간주
for _ in range(M):
    oper = input().strip()
    if oper[0] == 'P':
        p, alp = oper.split()
        node.addLeft(alp) # alp를 커서 왼쪽(현재 노드 왼쪽)에 추가함

    elif oper == 'L':
        # 커서를 왼쪽으로 한 칸 옮김
        if node.prev:
            node = node.prev

    elif oper == 'D':
        # 커서를 오른쪽으로 한 칸 옮김
        if node.next:
            node = node.next

    elif oper == 'B':
        # 커서 왼쪽에 있는 문자(현재 노드의 이전 노드)를 삭제함
        if node.prev:
            node.prev.delete()

while node.prev != None: # == 으로 적은 실수
    node = node.prev
while node.string != None:
    print(node.string, end='')
    node = node.next

풀긴 했는데 시간이 너무 느림

from sys import stdin

left = list(input())
right = []

for _ in range(int(input())):
    command = list(stdin.readline().split())
    if command[0] == 'L' and left:
        right.append(left.pop())
    elif command[0] == 'D' and right:
        left.append(right.pop())
    elif command[0] == 'B' and left:
        left.pop()
    elif command[0] == 'P':
        left.append(command[1])

answer = left + right[::-1]
print(''.join(answer))

다른 사람 풀이 보니까 커서 왼쪽과 오른쪽을 나누고

커서를 옮기는 건
커서 왼쪽을 나타내는 배열과
커서 오른쪽을 나타내는 배열의
한 쪽에서 빼낸 후에 다른 한 쪽에 더하는 식

아니 그러면 오른쪽은 append할 때 연산 비싼거 아닌가? 했는데
오른쪽 배열은 거꾸로 뒤집어놨다고 보면 됨
pop으로만 빼내므로 연산 비싸지 않다.