그림 1. 마지막 위치 데이터 삽입
code_test
algorithm
linked_list
stack
백준 1406번 텍스트 에디터 문제입니다. 이전에 따로 자료구조에 대해 정리를 해야할까 생각했지만 문제를 풀며 자료구조와 알고리즘의 활용 예시를 만들어 가는게 더 나을 것 같은 생각이 들었습니다. 문제는 온라인 프로그래밍 채점 사이트의 정답 비율이 30 % 보다 낮은 문제들을 이용하기로 했습니다.
한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000 글자까지 입력할 수 있다.
이 편집기에는 ‘커서’라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤 (마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳 (모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1 가지 경우가 있다.
이 편집기가 지원하는 명령어는 다음과 같다.
초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.
입력:
출력:
abcd
3
P x
L
P Y
abcdyx
abc
9
L
L
L
L
L
P x
L
B
P y
abcdyx
dmih
11
B
B
P x
L
B
B
B
P y
D
D
P z
yxz
Linked List는 조회는 느리지만(O(n)) 삽입, 제거가 유리한(O(1)) 자료구조입니다. 정 반대의 장점을 가진 자료구조로는 List 가 있습니다. List 는 인덱스를 통해 조회를 매우 빠르게(O(1)) 할 수 있지만 데이터를 삽입, 제거하기 위해서는 기존의 데이터들을 모두 이동시키는 과정(O(n))이 필요하므로 굉장히 느립니다.
만약 문제를 삽입, 제거가 느린 List 로 구현한다면 시간 내에 문제를 해결하지 못할 가능성이 큽니다. 또한 커서가 Linked List 내부에서 포인터의 역할을 하므로 List 의 인덱스를 활용한 조회는 필요가 없습니다. 즉, Linked List 를 활용하는 것이 좋은 방법입니다. 단, 문제의 특성상 커서가 오른쪽, 왼쪽 모두 이동하기 때문에 단방향 Singly Linked List 가 아닌 양방향 Doubly Linked List 를 활용해야 합니다.
Linked List에서 데이터를 삽입하려면 기존 데이터와 삽입할 데이터의 위치를 서로 업데이트하기만 하면 됩니다.
커서의 위치를 오른쪽, 왼쪽으로 이동하려면 참조를 따라가기만 하면 접근할 수 있습니다. 단 마지막 위치에 다다른다면 더 이상 이동할 수 없게 제어해야 합니다.
데이터를 제거하는 과정은 삽입의 역순입니다. 단, 왼쪽 끝 위치에 다다른다면 더 이상 제거할 수 없게 제어해야 합니다.
class Node:
def __init__(self, data):
self._data = data
self._pre = None
self._post = None
@property
def data(self):
return self._data
@property
def pre(self):
return self._pre
@pre.setter
def pre(self, node):
self._pre = node
@property
def post(self):
return self._post
@post.setter
def post(self, node):
self._post = node
class DoublyLinkedList:
def __init__(self, input):
self.head = Node(None)
self.tail = Node(None)
self._current = self.tail
self.head.post = self.tail
self.tail.pre = self.head
for data in input:
self.Insert(data)
@staticmethod
def Render(linked_list):
linked_list.current = linked_list.head.post
while (not linked_list.IsRightEnd):
print(linked_list.current.data, end="")
linked_list.current = linked_list.current.post
@property
def IsLeftEnd(self):
return (self.current.pre == self.head)
@property
def IsRightEnd(self):
return (self.current == self.tail)
@property
def current(self):
return self._current
@current.setter
def current(self, node):
self._current = node
def Insert(self, data):
new_node = Node(data)
left_node = self.current.pre
right_node = self.current
left_node.post = new_node
new_node.pre = left_node
new_node.post = right_node
right_node.pre = new_node
def MoveLeft(self):
if (not self.IsLeftEnd):
self.current = self.current.pre
def MoveRight(self):
if (not self.IsRightEnd):
self.current = self.current.post
def Delete(self):
if (not self.IsLeftEnd):
target_node = self.current.pre
left_node = target_node.pre
right_node = self.current
left_node.post = right_node
target_node.pre = None
target_node.post = None
right_node.pre = left_node
del (target_node)
def Solution(text, commands):
def CRLF():
print()
def DataRender(editor):
DoublyLinkedList.Render(editor)
CRLF()
editor = DoublyLinkedList(text)
functions = {"L": editor.MoveLeft,
"D": editor.MoveRight,
"B": editor.Delete,
"P": editor.Insert}
CRLF()
for command in commands:
print(command, end=" ")
if (command[0] != "P"):
functions[command[0]]()
else:
functions[command[0]](command[2])
current = editor.current
DataRender(editor)
editor.current = current
CRLF()
def main():
text = input()
m = int(input())
commands = []
for _ in range(m):
commands.append(input())
Solution(text, commands)
if __name__ == "__main__":
main()
Stack 도 자료의 추가와 제거가 O(1) 으로 굉장히 빠른 자료구조입니다. 2 개의 Stack 을 활용하면 커서의 위치 이동과 삽입, 제거를 더 간단하게 구현할 수 있습니다. 대신 Stack 의 크기를 미리 정해야 하하므로 메모리를 Linked List 에 비해 많이 사용하게 됩니다.
class Stack:
def __init__(self, N):
self.n = N
self.top = 0
self.buffer = [None] * self.n
@staticmethod
def Render(stack):
print(stack.buffer, end=" ")
@property
def IsEmpty(self):
return (self.top <= 0)
@property
def Peek(self):
return self.buffer[self.top - 1]
def Push(self, data):
self.buffer[self.top] = data
self.top += 1
def Pop(self):
self.top -= 1
data = self.buffer[self.top]
self.buffer[self.top] = None
return data
class TwoStack:
def __init__(self, input, extra):
stack_length = len(input) + extra
self.left_stack = Stack(stack_length)
self.right_stack = Stack(stack_length)
for data in input:
self.Insert(data)
@staticmethod
def Render(two_stack):
print("Left:", end=" ");
Stack.Render(two_stack.left_stack)
CRLF()
print("Right:", end=" ");
Stack.Render(two_stack.right_stack)
CRLF()
@property
def IsLeftEnd(self):
return (self.left_stack.IsEmpty)
@property
def IsRightEnd(self):
return (self.right_stack.IsEmpty)
def Insert(self, data):
self.left_stack.Push(data)
def MoveLeft(self):
if (not self.IsLeftEnd):
self.right_stack.Push(self.left_stack.Pop())
def MoveRight(self):
if (not self.IsRightEnd):
self.left_stack.Push(self.right_stack.Pop())
def Delete(self):
if (not self.IsLeftEnd):
self.left_stack.Pop()
def CRLF():
print()
def Solution(text, commands):
def DataRender(editor):
TwoStack.Render(editor)
editor = TwoStack(text, len(commands))
functions = {"L": editor.MoveLeft,
"D": editor.MoveRight,
"B": editor.Delete,
"P": editor.Insert}
CRLF()
for command in commands:
print(command)
if (command[0] != "P"):
functions[command[0]]()
else:
functions[command[0]](command[2])
DataRender(editor)
CRLF()
def main():
text = input()
m = int(input())
commands = []
for _ in range(m):
commands.append(input())
Solution(text, commands)
if __name__ == "__main__":
main()
Linked List 는 개인적으로 딥러닝 모델 커스터마이징 중 기존 형태에 새로운 Layer 를 추가할 때 사용한 경험이 있습니다. 나름 활용도가 높은 자료구조라 생각하며 딥러닝을 공부하시는 분이라면 굉장히 도움이 될 것입니다. 이만 포스트를 마치겠습니다. 감사합니다.