Baekjoon 1406. 에디터 / Python

1406. 에디터

난이도 : 실버 2
소요 시간 : 40분
날짜 : 2025.01.08
언어 : 파이썬
알고리즘 유형 : 연결리스트, 스택

설명 보기전에 문제 풀어보러 가기

1. 문제 설명

1. 주어진 문자를 주어진 명령에 따라 실행한 뒤, 마지막 남은 문자열을 출력한다.
2. 명령어는 커서를 기준으로 시작하고, 시작할 때의 커서는 맨 뒤이다.
   • L : 커서를 왼쪽으로 한 칸 (커서가 맨 앞이면 무시)
   • D : 커서를 오른쪽으로 한 칸 (커서가 맨 뒤이면 무시)
   • B : 커서 왼쪽 문자를 삭제 (커서가 맨 앞이면 무시)
   • P # : 커서 왼쪽에 # 이라는 문자 추가

2. 해결 방식

1. 연결리스트 연습을 위해 고른 문제인 만큼 연결리스트를 활용해서 풀이했다.(리스트에 insert를 하는 방법도 통과되는 듯....)
2. 연결리스트 기본 구조
   • Node : data-저장할 문자열, left - 왼쪽 항목, right - 오른쪽 항목
   • LinkedList : tail,head - 배열의 처음과 끝(None), start_node, end_node - 커서의 맨 앞 맨 뒤를 고려한 항목, cursor - 커서의 위치
3. 주의할 점 : 커서의 관리, 현재 커서가 맨 앞과 맨 뒤일 때의 처리
4. 함수별 구현
   • 첫 문자열 입력 : start_node, 노드들, 마지막노드, end_node의 배열에 new_node를 넣는 방식이다.
     new_node의 left,right에 마지막노드와 end_node를 할당해주고,
     마지막노드의 right, new_node의 left에 new_node를 할당해준다.
   • 커서이동 : cursor를 현재 연결리스트의 왼쪽, 오른쪽으로 이동해주면 끝.(이미 맨 앞이거나 맨 뒤인경우는 빼고 이동)
   • 커서 왼쪽에 추가 : 역시 new_node를 추가하는 방식이다.
   • 커서 왼쪽 제거 : (커서가 맨 왼쪽이 아닌 경우만) 제거할 노드를 선택하여 그 왼쪽과 오른쪽을 이어준다.

정답 코드에서는 실제 문자열의 첫노드와 마지막노드를 head, tail로 관리했는데 이 관련 코드는 빼도 될 것 같다..

3. 정답 코드

import sys
# input = sys.stdin.readline
sys.stdin = open("C:/Users/ghtjd/Desktop/tmp/python/input.txt", "r")

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class LinkedList():
    def __init__(self):
        self.tail = Node(None)
        self.head = Node(None)
        self.start_node, self.end_node = Node('start'), Node('end')
        self.start_node.right = self.tail

        self.tail.right = self.start_node
        self.head.left = self.end_node
        self.end_node.left = self.head

        self.cursor = self.start_node

    def initial_append(self, data):
        init_node = Node(data)
        init_node.right = self.end_node
        init_node.left = self.start_node
        self.end_node.left = init_node
        self.start_node.right = init_node
        self.tail = init_node
        self.head = init_node
        self.cursor = init_node.right

    def append(self, data):
        new_node = Node(data)
        new_node.left = self.tail
        new_node.right = self.end_node
        self.tail.right = new_node
        self.tail = new_node
        self.end_node.left = new_node
        self.cursor = new_node.right

    def insert_left(self, data):
        new_node = Node(data)
        new_node.right = self.cursor

        if self.cursor == self.start_node:
            prev = self.start_node
            self.head = new_node
        else:
            prev = self.cursor.left

        new_node.left = prev
        prev.right = new_node
        self.cursor.left = new_node

    def delete_left(self):
        if self.cursor.left != self.start_node:
            del_node = self.cursor.left
            prev = del_node.left
            next = del_node.right
            prev.right = next
            next.left = prev
            if del_node == self.head:
                self.head = next

    def move_cursor_left(self):
        if self.cursor != self.start_node.right:
            self.cursor = self.cursor.left

    def move_cursor_right(self):
        if self.cursor != self.end_node:
            self.cursor = self.cursor.right

    def print(self):
        res, now = [], self.start_node
        now = now.right
        while now != self.end_node:
            res.append(now.data)
            now = now.right
        print(''.join(res))

if __name__ == '__main__':
    char = input().strip()

    arr = LinkedList()
    arr.initial_append(char[0])
    for i in range(1, len(char)):
        arr.append(char[i])

    for _ in range(int(input())):
        c = input().split()
        if c[0] == 'L':
            arr.move_cursor_left()
        elif c[0] == 'D':
            arr.move_cursor_right()
        elif c[0] == 'B':
            arr.delete_left()
        else:
            arr.insert_left(c[1])

    arr.print()