[프로그래머스] 2021 카카오 인턴십 - 표 편집 (Python)

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/81303

나의 풀이

• Linked List를 이용하여 주어진 조건들을 구현하면 된다
• 각 노드들에는 [prev, next, is_deleted]로 마지막 원소는 최종적으로 삭제되었는지를 판단하기 위해 추가했다.
• 되돌리기 명령어를 위해 deleted라는 stack을 이용한다.

배열로 풀게 되면 입력 노드들의 개수가 최대 1,000,000개, 명령어는 최대 200,000개라 삭제, 되돌리기 명령어 때문에 시간 초과가 날 수 있기 때문에 Linked List로 풀어야 한다.

Code

#https://programmers.co.kr/learn/courses/30/lessons/81303

def solution(n, k, command):
    # prev, next, is_delete
    linked_list = {i: [i - 1, i + 1, 0] for i in range(n)}
    deleted = []

    curr = k

    for cmd in command:
        if cmd[0] == 'U':
            move = int(cmd[2:])
            for i in range(move):
                curr = linked_list[curr][0]

        elif cmd[0] == 'D':
            move = int(cmd[2:])
            for i in range(move):
                curr = linked_list[curr][1]

        elif cmd[0] == 'C':
            prev, next, is_deleted = linked_list[curr]
            deleted.append([prev, next, curr])
            # 젤 위 요소 삭제
            if prev == -1:
                linked_list[next][0] = prev
                linked_list[curr][2] = 1
                curr = next

            # 젤 아래 요소 삭제
            elif next == n:
                linked_list[prev][1] = next
                linked_list[curr][2] = 1
                curr = prev
            # 중간 요소 삭제
            else:
                linked_list[prev][1] = next
                linked_list[next][0] = prev
                linked_list[curr][2] = 1
                curr = next

        else:
            prev, next, origin = deleted.pop()
            if prev == -1:
                linked_list[next][0] = origin
                linked_list[origin][2] = 0
            elif next == n:
                linked_list[prev][1] = origin
                linked_list[origin][2] = 0
            else:
                linked_list[prev][1] = origin
                linked_list[next][0] = origin
                linked_list[origin][2] = 0

    answer = ''

    for prev, next, is_deleted in linked_list.values():
        if is_deleted:
            answer += 'X'
        else:
            answer += 'O'
    return answer

Git

https://github.com/youngh0/Algorithm/blob/master/kakao/2021_internship/LV3_edit_table.py