class Node:
def __init__(self):
self.num = 0
self.removed = False
self.prev = None
self.next = None
def solution(n, k, cmd):
list = [Node() for _ in range(n)]
stack =[]
for i in range(1,n):
list[i].num = i
list[i-1].next = list[i]
list[i].prev = list[i-1]
current = list[k]
for command in cmd:
option = command[0]
if (option == 'U'):
amount = int(command.split(" ")[1])
for i in range(amount):
current = current.prev
elif (option == 'D'):
amount = int(command.split(" ")[1])
for i in range(amount):
current = current.next
elif (option == 'C'):
stack.append(current.num)
current.removed= True
if(current.prev):
current.prev.next = current.next
if(current.next):
current.next.prev = current.prev
current = current.next
else:
current = current.prev
elif (option == 'Z'):
pop = stack.pop()
restore = list[pop]
restore.removed = False
if(restore.prev):
restore.prev.next = restore
if(restore.next):
restore.next.prev = restore
answer =''
for item in list:
if(item.removed):
answer+='X'
else:
answer+='O'
return answer풀이
자료구조
더블 링크드 리스트를 사용하여 구현하였다. 하나의 노드에는 이전 노드를 가리키는 prev , 인덱스를 가리키는 Num , 제거되었는지를 나타내는 Removed 그리고 다음 노드를 가리키는 next 로 구성되어있다.
1. U 명령어
U command 같은 경우 간단하다 문제에서 범위를 벗어나는 옵션은 주어지지 않는다고 하였으므로 변수를 해당 숫자 만큼 prev 를 참조하면 된다.
2. D 명령어
D command 같은 경우도 U와 동일하게 next를 참조하면 된다.
3. C 명령어
C command의 경우 주의가 필요하다.
current가 가리키는 노드의 prev 노드의 next를 current 다음 노드로 연결하고
current가 가리키는 노드의 next 노드의 prev를 current의 이전 노드로 연결해주고 current를 다음 노드로 할당해준다.
이 때 2가지를 고려해야 하는데 바로 current 이전 노드가 없을 경우와 current 이후 노드가 없을 경우이다.
current 이전 노드가 없을 경우 current 이후 노드의 prev를 None 으로 설정해준다.
current 이후 노드가 없을 경우 current 이전 노드의 next를 None 으로 설정해준다. 그리고 current를 이전 노드로 할당한다
추가로 Z커맨드로 되돌리기시 최근 삭제한 노드부터 되돌리기하므로 스택 자료구조를 할당해서 몇번째노드가 삭제되었는지 기록한다.
4. Z 명령어
Z command는 stack 에서 하나의 Num을 빼내고 다시 링크드 리스트에 연결시켜주면 된다.
복구한 노드 이전 노드의 next를 복구한 노드로, 이후 노드의 prev를 동일하게 복구한 노드로 연결시켜주면 된다.
