1. 아이디어
문제에서 주어진 표를 Double linked list로 표현한다. 나의 경우 아래의 그림처럼 표현했다.
header와 tail를 두는 이유는 node 0의 왼쪽 링크가, node 2의 오른쪽 링크가 None을 가리키는게 마음에 안들어서 추가했다. 같은 이유로 header의 왼쪽 링크에 header 자신을 넣었고 tail의 오른쪽 링크에 tail 자신을 넣었다.
pointer는 명령어(U, D, C)에 의해 현재 가리키고 있는 node를 의미한다. 명령어를 입력받지 않는 초기에는 k값이 노드를 가리키는 위치이다. 아마 많은 사람들이 이동 명령어보다는 삭제(C), 복구(Z) 명령어(최근에 삭제된 node를 복원)에 관심이 많을 것이다.
pointer가 가리키는 위치를 지운다고 하자. 그렇게 되면, node 1의 오른쪽 링크는 tail을 가리키고, tail의 왼쪽 링크는 node 1를 가리키게 될 것이다. 그리고 node 2는 복구 명령어에서 사용될 stack에 저장될 것이다. 여기서 주의할 점은 node 2의 왼쪽 링크와 오른쪽 링크를 끊지 않고 stack에 저장하는 것이다. 그래야 복구 명령어 때, node를 하나하나 방문하지 않고 바로 연결할 수 있다. 따라서, node 2를 지우면 아래와 같다.
위의 그림에서 node 2의 다음 node는 존재하지 않기 때문에, pointer는 node 1를 가리킨다. 여기서 node 1를 삭제하자. 그러면 아래의 그림과 같다.
여기서 복원을 하면 아래의 그림과 같다.
stack에서 pop하여 node 1을 가져오고 node 1의 왼쪽 링크, 오른쪽 링크를 이용하여 node 0과 tail을 잇는다. 아래의 코드처럼 말이다.
restored_node = stack.pop()
restored_node.left.right = restored_node
restored_node.right.left = restored_node따라서 double linked list에서 삭제 명령어에 의해 pointer가 가리키는 node를 지울 때, 해당 node의 왼쪽 링크, 오른쪽 링크는 유지하면서 stack에 저장하자. 삭제 명령어를 할 때, pointer가 가리킬 다음 노드가 어딘지 주의해서 구현을 하면된다.
이동 명령어 구현은 생략한다. 그리고 정답을 구할 때는 길이 n의 배열을 만들어서 모든 원소를 X로 초기화한다. 이후 Double linked list에 있는 node들을 방문하면서 배열[node 숫자] = 'O'로 하면된다. 그리고 문자열로 합쳐서 반환한다.
2. 코드
class Node:
def __init__(self, data=None, state=1):
self.data = data
self.right = None
self.left = None
class DoubleLinkedList:
def __init__(self):
self.header = Node()
self.tail = Node()
self.header.right = self.tail
self.header.left = self.header
self.tail.right = self.tail
self.tail.left = self.header
self.pointer = self.header
def add(self, node):
self.pointer.right = node
node.left = self.pointer
node.right = self.tail
self.pointer = node
def move(self, pointer, v, step):
for _ in range(step):
if v == 'D': pointer = pointer.right
else: pointer = pointer.left
return pointer
def delete(self, pointer):
if pointer.left == self.header:
self.header.right = pointer.right
pointer.right.left = self.header
return self.header.right
elif pointer.right == self.tail:
_pointer = pointer.left
self.tail.left = _pointer
_pointer.right = self.tail
return _pointer
else:
_pointer = pointer.right
pointer.left.right = pointer.right
pointer.right.left = pointer.left
return _pointer
def insert(self, pointer):
pointer.left.right = pointer
pointer.right.left = pointer
def get_answer(n, linkedlist):
answer = ['X' for _ in range(n)]
pointer = linkedlist.header.right
while pointer != linkedlist.tail:
answer[pointer.data] = 'O'
pointer = pointer.right
return ''.join(answer)
def solution(n, k, cmd):
answer = ''
linkedlist = DoubleLinkedList()
pointer = linkedlist.header
stack = []
for i in range(n): linkedlist.add(Node(i))
while pointer.data != k: pointer = pointer.right
for string in cmd:
if string == 'C':
stack.append(pointer)
pointer = linkedlist.delete(pointer)
elif string == 'Z':
_pointer = stack.pop()
linkedlist.insert(_pointer)
else:
v, step = string.split()
pointer = linkedlist.move(pointer, v, int(step))
answer = get_answer(n, linkedlist)
return answer