[BOJ] 1406: 에디터

1. problem :

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

 

2. solution 1 :

import sys
input = sys.stdin.read

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

class DoublyLinkedList:
    def __init__(self):
        dummy_node = Node(0)
        self.head = dummy_node
        self.tail = dummy_node
    
    def erase(self, current_node):
        if current_node == self.head:  # dummy 노드를 지우지 않기 위해 아무것도 하지 않음
            return self.head
        
        if current_node.next:  # current_node.next가 있을 경우 prev 업데이트
            current_node.next.prev = current_node.prev
        if current_node.prev:  # current_node.prev가 있을 경우 next 업데이트
            current_node.prev.next = current_node.next
        
        if current_node == self.tail:  # tail 노드 삭제 시 tail 업데이트
            self.tail = current_node.prev

        return current_node.prev  # current_node.prev로 커서 이동

    def insert(self, current_node, val: int):
        new_node = Node(val)
        new_node.next = current_node.next
        new_node.prev = current_node

        if current_node.next is not None:  # current_node.next가 있을 경우 prev 업데이트
            current_node.next.prev = new_node
        else:  # current_node.next가 없을 경우 tail 업데이트
            self.tail = new_node

        current_node.next = new_node
        return new_node  # 새로 삽입된 노드로 커서 이동

def main():
    data = input().split()
    initial_string = data[0]
    commands = data[1:]
    
    ll = DoublyLinkedList()
    current_node = ll.head
    for ch in initial_string:
        current_node = ll.insert(current_node, ch)
    
    i = 0
    while i < len(commands):
        command = commands[i]
        if command == 'P':
            i += 1
            current_node = ll.insert(current_node, commands[i])
        elif command == 'B':
            current_node = ll.erase(current_node)
        elif command == 'L':
            if current_node.prev is not None:
                current_node = current_node.prev
        elif command == 'D':
            if current_node.next is not None:
                current_node = current_node.next
        i += 1

    result = []
    temp = ll.head.next
    while temp:
        result.append(temp.val)
        temp = temp.next
    
    print(''.join(result))

if __name__ == "__main__":
    main()

doubly_linked_list의 class를 형성한 후, erase, insert method를 만들었다. 그 후, 문제를 풀었다. 

입출력에 처음에는 input()으로 받았는데, 시간 초과가 났다. sys.stdin으로 하니, 통과되었다. 

 

3. solution 2 :

import sys 
input = sys.stdin.read

def main():
    data = input().split()
    initial_string = data[0]
    commands = data[2:]
    left_stack = list(initial_string)
    right_stack = []

    index = 0 
    while index < len(commands):
        command = commands[index]
        if command == "L":
            if left_stack:
                right_stack.append(left_stack.pop())
        elif command == "D":
            if right_stack:
                left_stack.append(right_stack.pop()) 
        elif command == "P":
            index += 1 
            left_stack.append(commands[index])
        else:
            if left_stack:
                left_stack.pop()
        index += 1 
    
    print(''.join(left_stack) + ''.join(right_stack[::-1]))

if __name__ == "__main__":
    main()

stack을 이용한 방법. 훨씬 쉬운 방법이다. 코드도 짧고, 실행시간도 빠르고, 메모리도 적게 잡아먹는다.