(Python) 프로그래머스 - 표 편집

in Algorithm on Programmers, Level3

[문제 링크]

풀이

def solution(n, k, cmd):
    linked_list = dict()
    linked_list[0] = [None, 1]
    linked_list[n - 1] = [n - 2, None]
    for i in range(1, n - 1):
        linked_list[i] = [i - 1, i + 1]

    delete_stack = []
    answer = ["O"] * n

    for operations in cmd:
        operation = operations.split()
        if operation[0] == 'D':
            for _ in range(int(operation[1])):
                k = linked_list.get(k)[1]
        elif operation[0] == 'U':
            for _ in range(int(operation[1])):
                k = linked_list.get(k)[0]
        elif operation[0] == 'C':
            delete_stack.append(k)
            prev, next = linked_list.get(k)

            if next == None:
                k = prev
            else:
                k = next
            if next == None:
                linked_list.get(prev)[1] = None
            elif prev == None:
                linked_list.get(next)[0] = None
            else:
                linked_list.get(prev)[1] = next
                linked_list.get(next)[0] = prev
        else:
            restore_idx = delete_stack.pop()
            prev, next = linked_list.get(restore_idx)
            if prev == None:
                linked_list.get(next)[0] = restore_idx
            elif next == None:
                linked_list.get(prev)[1] = restore_idx
            else:
                linked_list.get(prev)[1] = restore_idx
                linked_list.get(next)[0] = restore_idx

    for x in delete_stack:
        answer[x] = "X"

    return "".join(answer)
  1. 순서대로 복원해야한다는 점에서 스택을 사용해야 한다는 것을 눈치챈다.
  2. 복원 시 이전의 위치 그대로 들어가야 한다. 배열을 사용할 경우 복잡도가 높아지므로 링크드 리스트 사용을 눈치챈다.

파이썬에서 링크드리스트 사용을 어떻게 해야 하는지 몰라서 고민했는데 다른 분들 풀이를 보니 딕셔너리를 사용해서 링크드리스트를 구현하고 있어 참고했다.

© 2021. By Backtony