2021 카카오 채용연계형 인턴십 3번

park2348190·2021년 5월 10일
0

설명

[ 문제 비공개 ]

풀이

import collections


class Node:
    def __init__(self): # double linked list
        self.prev_node = None
        self.next_node = None


def solution(n, k, cmd):
    stack = collections.deque() # 삭제 목록 저장.
    archive = collections.deque()
    # archive에는 노드들을 저장. 나중에 꺼내서 initial_node에서 연결된 노드들을 따라가면서 비교.
    
    initial_node = Node()
    archive.append(initial_node)
    prev_node = initial_node
    
    for index in range(1, n):
        generated_node = Node()
        prev_node.next_node = generated_node
        generated_node.prev_node = prev_node
        archive.append(generated_node)
        prev_node = generated_node
    
    current_node = initial_node
    for _ in range(k):
        current_node = current_node.next_node
    
    for cmd_string in cmd:
        command = cmd_string[0]
        if command == "U" or command == "D":
            value = int(cmd_string.split(" ")[1])
            for _ in range(value):
                current_node = current_node.prev_node if command == "U" else current_node.next_node
        elif command == "C":
            stack.append(current_node)
            if current_node.next_node:            
                # [ 1 ][ 2(X) ][ 3 ]에서 현재 행을 삭제할 경우
                # 이전 노드가 있으므로 이전 노드와 다음 노드를 연결.
                # 포인터는 다음 노드로 이동.
                if current_node.prev_node:
                    current_node.prev_node.next_node = current_node.next_node
                    current_node.next_node.prev_node = current_node.prev_node
                    current_node = current_node.next_node
                    
                # [ 2(X) ][ 3 ]에서 현재 행을 삭제할 경우
                # 이전 노드가 없으므로 단순히 다음 노드로 이동.
                else:
                    current_node.next_node.prev_node = None
                    current_node = current_node.next_node
                    initial_node = current_node      
            else: 
                # [ 1 ][ 2(X) ]에서 현재 행을 삭제할 경우
                # 다음 노드가 없으므로 이전 노드로 이동.
                current_node.prev_node.next_node = None
                current_node = current_node.prev_node
        elif command == "Z":
            deleted_node = stack.pop()
            previous_node = deleted_node.prev_node
            next_node = deleted_node.next_node
            
            # edge case for deleted node is first node.
            if previous_node is None:
                initial_node.prev_node = deleted_node
                deleted_node.next_node = initial_node
                initial_node = initial_node.prev_node
                continue
            
            previous_node.next_node, deleted_node.next_node = deleted_node, previous_node.next_node
            if deleted_node.next_node:
                deleted_node.next_node.prev_node = deleted_node
            
    # compare
    answer = []
    while archive:
        if archive.popleft() is initial_node:
            answer.append("O")
            initial_node = initial_node.next_node
        else:
            answer.append("X")
        
    return "".join(answer)

이중 연결 리스트로 구축하여 풀 수 있었는데 정말 오랜만에 다뤄보는 자료구조인데다 이중이라 이것저것 신경쓸 일이 많아서 기력도 많이 소모하고 코드 중복 여부도 확인하지 못했다.

특히 복구 연산("Z")에서 시간 초과때문에 좀 고민했었는데 처음에는 previous_node를 처음부터 탐색해서 다시 연결하는 방식이었지만 생각해보니 어차피 원래 노드 객체 그 자체라 굳이 그럴 필요가 없어서 바로 참조하는 방식으로 개선하였다.

여기까지 풀고나니 지쳐서 4번, 5번은 건드릴 엄두도 내지 못했기 때문에 많이 아쉽다. 하지만 4번, 5번이 많이 어려워보이던데 여기까지가 내 한계일지도 모른다.

profile
YUKI.N > READY?

관심 있을 만한 포스트

0개의 댓글