표 편집

class Node(): def __init__(self, data): self.prev, self.next = None, None self.data = data self.deleted = False def append(self, node): self.next = node node.prev = self def delete(self): # 이 노드가 삭제되었음을 나타내고, self.deleted = True # 전후 노드의 연결관계를 업데이트합니다. if self.prev is None: self.next.prev = None elif self.next is None: self.prev.next = None else: prev, next = self.prev, self.next self.prev.next = next self.next.prev = prev # 마지막 노드이면, 이전 노드를 리턴합니다. if self.next is None: return self.prev # 그렇지 않으면, 다음 노드를 리턴합니다. else: return self.next def revert(self): # 복구합니다. self.deleted = False # 먼저 prev이 어떤 노드를 가리켜야 할지 봅시다. # 우선 원래 가리키던 prev을 보는데, prev = self.prev # 만약 이 prev이 역시 deleted이면 # 그 node의 prev을 내 prev로 삼아야 합니다. while prev is not None and prev.deleted: prev = prev.prev self.prev = prev next = self.next # 만약 이 next가 역시 deleted이면 # 그 node의 next을 내 next로 삼아야 합니다. while next is not None and next.deleted: next = next.next self.next = next # prev와 next의 연결 관계를 업데이트합니다. if prev is not None: self.prev.next = self if next is not None: self.next.prev = self def solution(n, k, cmd): head = Node(data=-1) # head prev = head for data in range(n): node = Node(data=data) prev.append(node) prev = node if data == k: curr = node deleted_nodes = [] for op in cmd: tokens = op.split() if tokens[0] == 'U': # 위로 이동합니다. for _ in range(int(tokens[1])): curr = curr.prev elif tokens[0] == 'D': # 아래로 이동합니다. for _ in range(int(tokens[1])): curr = curr.next elif tokens[0] == 'C': # 삭제합니다. deleted_nodes.append(curr) curr = curr.delete() elif tokens[0] == 'Z': node = deleted_nodes.pop() node.revert() answer = ['X'] * n curr = head while curr.next is not None: if curr.data != -1: # head는 답안에 포함시키지 않습니다. answer[curr.data] = 'O' curr = curr.next answer[curr.data] = 'O' return ''.join(answer)