[코딩테스트] 백준 - 에디터

---

문제

 

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

1406번: 에디터

 

 커서를 L, D, B, P 명령어를 통해 이동하거나 커서 왼쪽에 문자를 삭제하고 추가하고 최종 결과를 출력하는 문제

---

전략

 

01. 리스트

 

import sys

string = list(sys.stdin.readline().rstrip())
M = int(sys.stdin.readline().rstrip())

cursor = len(string)

for _ in range(M):
    ins = sys.stdin.readline().rstrip().split()

    if ins[0] == 'L':
        if cursor != 0:
            cursor -= 1
    elif ins[0] == 'D':
        if cursor < len(string):
            cursor += 1
    elif ins[0] == 'B':
        if cursor != 0:
            del string[cursor-1]
            cursor -= 1
    elif ins[0] == 'P':
        string.insert(cursor, ins[1])
        cursor += 1

print(''.join(string))

 

 시간제한이 0.3초라서 시간초과가 발생했다.

 

 

02. deque

 데크가 더블리 링크드 리스트로 구현되어 있으므로 이걸 이용하면 되지 않을까 싶었는데, 커서 왼쪽의 문자를 삭제하는 메소드가 따로 없었다. 데크에는 첫번째 값을 삭제하는 remove메소드 밖에 없었으므로 탈락

 

 

03. Doubly Linked List

 직접 구현하기로 했다.

 

 

 

---

풀이

 

import sys


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

    def __str__(self) -> str:
        return str(self.data)


class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.cursor = None

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
            self.cursor = new_node

    def delete(self):
        if self.cursor:
            if self.cursor == self.tail:
                self.tail = self.cursor.prev
                self.tail.next = None
                self.cursor = self.cursor.prev
            elif self.cursor == self.head:
                self.head = self.cursor.next
                self.head.prev = None
                self.cursor = None
            else:
                self.cursor.prev.next = self.cursor.next
                self.cursor.next.prev = self.cursor.prev
                self.cursor = self.cursor.prev

    def move_cursor(self, ins):
        if ins == 'L':
            if self.cursor == self.head:
                self.cursor = None
            elif self.cursor is None:
                pass
            else:
                self.cursor = self.cursor.prev
        elif ins == 'D':
            if self.cursor is None:
                self.cursor = self.head
            elif self.cursor == self.tail:
                pass
            else:
                self.cursor = self.cursor.next

    def insert(self, data):
        new_node = Node(data)

        if self.cursor:
            if self.cursor.next:
                new_node.next = self.cursor.next
                new_node.prev = self.cursor
                self.cursor.next.prev = new_node
                self.cursor.next = new_node
            else:
                self.cursor.next = new_node
                new_node.prev = self.cursor
                self.tail = new_node
            self.cursor = new_node
        else:
            if self.head:
                new_node.next = self.head
                self.head.prev = new_node
                self.head = new_node
                self.cursor = new_node
            else:
                self.head = new_node
                self.tail = new_node
                self.cursor = new_node

    def __str__(self):
        result = []
        iterator = self.head
        while iterator:
            result.append(iterator.data)
            iterator = iterator.next
        return ''.join(result)


string = DoublyLinkedList()

for i in sys.stdin.readline().rstrip():
    string.append(i)

string.cursor = string.tail

M = int(sys.stdin.readline().rstrip())

for _ in range(M):
    ins = sys.stdin.readline().split()
    if ins[0] == 'L':
        string.move_cursor('L')
    elif ins[0] == 'D':
        string.move_cursor('D')
    elif ins[0] == 'B':
        string.delete()
    elif ins[0] == 'P':
        string.insert(ins[1])

print(string)

 

 커서의 위치에 따른 제한이 너무 많아서 많이 힘들었다. 커서가 맨왼쪽에 있을 경우, 커서가 중간 어느 위치에 있을 경우, 커서가 맨 오른쪽에 있을 경우에 따라 각 메소드의 분기문을 잔뜩 만들어 줘서 풀었다.

 

 

---

다른 사람의 풀이

 

1. 두 개의 스택

import sys

left_stack = list(input().rstrip())  # 커서의 왼쪽에 있는 문자들
right_stack = []  # 커서의 오른쪽에 있는 문자들
m = int(input())

for _ in range(m):
    cmd = sys.stdin.readline().rstrip()
    
    if cmd[0] == 'L':
        if left_stack:
            right_stack.append(left_stack.pop())
            
    elif cmd[0] == 'D':
        if right_stack:
            left_stack.append(right_stack.pop())
            
    elif cmd[0] == 'B':
        if left_stack:
            left_stack.pop()
            
    elif cmd[0] == 'P':
        left_stack.append(cmd[2])

# 마지막으로 남아있는 문자들을 결합
print(''.join(left_stack + right_stack[::-1]))

 

 커서를 기준으로 왼쪽 문자를 표현하는 왼쪽 스택과 오른쪽 문자를 표현하는 오른쪽 스택을 만들어서 풀었다.

 

 먼저 왼쪽 스택에 문자를 전부 넣은 뒤, 커서가 왼쪽으로 이동할 때 왼쪽 스택의 문자를 오른쪽 스택으로 옮겨주는 식이다.

 

 엄청 좋은 풀이다.