[프로그래머스] 카카오 편집 샵

아이디어 도출 방법

해당하는 문제를 읽다가 보면 양방향 연결 리스트 느낌을 받을 수 있다. 왜냐하면 양방향 연결 리스트의 특징을 생각해보면 노드를 찾는 과정에서 o(n), 삭제 및 삽입 과정에서는 o(1)이 되도록 구현할 수 있기 때문이다.

또한 이번 문제에서는 특정 노드를 탐색하는 과정 없이, 지시에 따라서 현재 무슨 노드(파란색)에 위치하고 있는지만 체크하면 된다. 문제에서 원하는 복구 과정 역시 스택을 떠올리면 쉽게 해결할 수 있다, 스택은 선입 후출의 자료구조로 나중에 들어오는 것이 빨리 나간다.

한 가지 까다로운 점은 복구하는 과정이었다. 처음에는 삭제한 노드에서 가장 가까이 살아있는 노드를 찾는 방법을 사용해 삭제된 노드를 다시 삽입하려고 했지만 시간 초과가 발생했다. 하지만 다시 생각해보니 양 옆 노드를 같이 저장하면 쉽게 복구할 수 있었다. 왜냐하면  나머지 연산이 링크 리스트의 변경을 가하지 않기 때문이다.

from collections import deque

def get_next_pos(cache, my_pos, mv_cnt=1, foward=True):

    for _ in range(mv_cnt):
        if foward:
            next_pos = cache[my_pos][1]
        else:
            next_pos = cache[my_pos][0]

        my_pos = next_pos
    
    return my_pos

def solution(n, my_pos, cmds):
    answer = ''

    origin_array = [[i, True] for i in range(n)]
    cache_table = []        #o back 1 forward
    
    for i in range(n):
        cache_table.append([i -1, i + 1])

    cache_table[0] = [None , 1]
    cache_table[n-1] = [n-2, None]

    remove_stack = deque()

    for cmd in cmds:
        if len(cmd.split()) > 1:
            mv, mv_cnt = cmd.split()
            mv_cnt = int(mv_cnt)

            if mv == "D":
                next_pos = get_next_pos(cache_table, my_pos, mv_cnt)     #앞으로 전진 None 확률 없음
            else:
                next_pos = get_next_pos(cache_table, my_pos, mv_cnt, foward=False)

            my_pos = next_pos
        else:
            if cmd[0] == 'C':
                origin_array[my_pos][1] = False
                back_pos, forward_pos = cache_table[my_pos]

                #몸통
                if back_pos != None and forward_pos != None:
                    cache_table[back_pos][1] = forward_pos
                    cache_table[forward_pos][0] = back_pos
                else:
                    #머리
                    if forward_pos != None: #back은 None임
                        cache_table[forward_pos][0] = None
                    else: #꼬리
                        cache_table[back_pos][1] = None

                remove_stack.append((back_pos, my_pos, forward_pos))

                if forward_pos == None:
                    my_pos = back_pos
                else:
                    my_pos = forward_pos

            if cmd[0] == "Z":
                back_pos, pos, forward_pos = remove_stack.pop()
                
                #몸통
                if back_pos != None and forward_pos != None:
                    cache_table[forward_pos][0] = pos
                    cache_table[back_pos][1] = pos
                else:
                    #머리
                    if forward_pos != None: #back은 None임
                        cache_table[forward_pos][0] = pos
                    else: #꼬리
                        cache_table[back_pos][1] = pos


                origin_array[pos][1] = True

        # print("my pos is", my_pos)
        # print(origin_array)
        # print(cache_table)

    answer = ''

    for _, is_alive in origin_array:
        if is_alive:
            answer += "O"
        else:
            answer += "X"

    return answer




if __name__ == "__main__":
    n = 8
    k = 2
    cmd = ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"]

    print(solution(n, k, cmd))

후기

개념은 쉽지만 구현이 상당히 어려웠다. 오랫만에 양방향 연결 리스트를 구현하니 자꾸 Key index Error가 발생해 좀 더 구조적으로 나눠서 접근했다. 양방향 연결 리스트의 개념을 복습할 수 있어서 좋은 문제였다. 쉬운 것 같지만 어려운 문제였다.