[Python] BOJ 1406 - 에디터(Doubly Linked List)

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

1406번: 에디터

처음에 단순히 전에 풀었던 스택/큐/덱 문제처럼 접근해서 리스트로 풀었더니 시간 초과가 나왔다.

list.insert가 O(n)이고 list.pop(k)가 O(k)여서 시간초과가 나오는 듯하다.

스택 2개를 사용하여 왔다갔다 해주면 짧고 빠르게 풀 수 있지만, 문제 분류도 '링크드 리스트'이고 
공부할 겸 이중연결리스트로 풀어봤다.

import sys
input = sys.stdin.readline
class DList:
    class Node:
        def __init__(self,item,prev,link):
            self.item = item
            self.prev = prev
            self.next = link

    def __init__(self):
        self.head = self.Node(None,None,None)
        self.tail = self.Node(None,self.head,None)
        self.head.next = self.tail
        self.cur = self.tail

    def insert(self,p,item):
        t = p.prev
        n = self.Node(item,t,p)
        p.prev = n
        t.next = n

    def delete(self,x):
        f = x.prev
        r = x.next
        f.next = r
        r.prev = f

    def print_list(self):
        p = self.head.next
        while p != self.tail:
            if p.next != self.tail:
                print(p.item, end="")
            else:
                print(p.item)
            p = p.next

s = list(input().rstrip())
dl = DList()
for i in range(len(s)):
    dl.insert(dl.tail,s[i])

for i in range(int(input())):
    o = input()
    if(o[0] == "L"):
        if(dl.cur.prev.prev != None):
            dl.cur = dl.cur.prev
    elif(o[0] == "D"):
        if(dl.cur.next != None):
            dl.cur = dl.cur.next
    elif(o[0] == "B"):
        if(dl.cur.prev.prev != None):
            dl.delete(dl.cur.prev)
    else:
        dl.insert(dl.cur,o[2])
dl.print_list()

코드도 길고 복잡하지만 며칠동안 고민하면서 푸니 이제 좀 연결리스트가 이해가 된 것 같다.