[TIL] 백준 1406번: 에디터 (Python) - 연결리스트로 풀기

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

1406번: 에디터

 

 

 

 

  풀이 방법

다른 사람들의 풀이를 보면 두 개의 스택을 이용하는 방법이 많은데, 현재 공부 중인 바킹독 시리즈에서 연결 리스트 문제로 분류되어있어 연결리스트로 구현하여 제출하였다.

그냥 리스트를 사용하는 것보다 insert시에 시간이 O(N)이 아닌 O(1)이라 문제의 빡빡한 시간 제한을 통과할 수 있으며, 연결리스트 내의 다양한 메서드를 구현할 수 있지만 문제에서 필요로하는 최소한의 요소만 넣으려면 insert, delete, print만 구현하면 될 것 같다. 

1. 커서를 연결리스트의 tail에 둔다.
2. 처음 입력받은 문자열을 모두 연결리스트에 insert
3. print시에 커서 위치부터 출력되기 위해 커서는 head가 되어서는 안된다.
   • 따라서 왼쪽으로 커서 이동시에 prev의 prev가 null이 아니어야 (옮겨질 커서의 앞이 적어도 head) 커서를 이동한다.
4. 오른쪽으로 커서 이동시에는 커서 위치가 tail이어도 되므로 (출력시 tail 전까지 출력) 그냥 이동한다.
5. insert시에는 커서 위치 기준으로 왼쪽에 삽입 구현
6. delete시에는 커서위치의 좌 우를 서로 연결

 

  코드

import sys


class Node(object):
    def __init__(self, data, prev = None, next = None):
        self.data = data
        self.prev = prev
        self.next = next

class DList(object):
    def __init__(self):
        self.head = Node(None)
        self.tail = Node(None, self.head)
        self.head.next = self.tail
        self.cur = self.tail
    
    def insert(self, node, data):
        tmp_prev = node.prev
        newNode = Node(data, tmp_prev, node)
        tmp_prev.next = newNode
        node.prev = newNode
        
    def delete(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        del node
    
    def print_list(self):
        target = self.head.next
        while target != self.tail:
            if target.next != self.tail:
                print(target.data, end='')
            else:
                print(target.data)
            target = target.next


string = sys.stdin.readline().strip()
dl = DList()
for ch in string:
    dl.insert(dl.tail, ch)

for i in range(int(sys.stdin.readline().strip())):
    o = sys.stdin.readline().strip()
    if o[0] == "L":
        if dl.cur.prev.prev:
            dl.cur = dl.cur.prev
    elif o[0] == "D":
        if dl.cur.next:
            dl.cur = dl.cur.next
    elif o[0] == "B":
        if dl.cur.prev.prev:
            dl.delete(dl.cur.prev)
    else: # "P"
        dl.insert(dl.cur, o[2])
dl.print_list()

 

  시간 초과 시 팁

처음에는 input으로 입력을 받았는데, 시간 초과가 발생하였고 sys.stdin.readline() 으로 받을 경우 통과할 수 있다.