프로그래머스 - 표 편집 (2021 카카오 채용연계형 인턴십) / Level 3

문제 📋

코딩테스트 연습 - 표 편집

풀이 📝

def solution(n, k, cmd):
    table = {x : [x-1, x+1] for x in range(n)}
    answer = ['O' for _ in range(n)]
    clear = []
    
    for c in cmd:
        detail = c.split()
        
        if detail[0] == 'C':
            before, after = table[k]
            clear.append((before, after, k))
            answer[k] = 'X'
            
            if before == -1:
                table[after][0] = before
                k = after
            elif after == n:
                table[before][1] = after
                k = before
            else:
                table[before][1] = after
                table[after][0] = before
                k = after
        elif c == 'Z':
            before, after, num = clear.pop()
            answer[num] = 'O'
            
            if before == -1:
                table[after][0] = num
            elif after == n:
                table[before][1] = num
            else:
                table[before][1] = num
                table[after][0] = num
        
        elif detail[0] == 'U':
            for _ in range(int(detail[1])):
                k = table[k][0]
        elif detail[0] == 'D':
            for _ in range(int(detail[1])):
                k = table[k][1]
        
            
    return ''.join(answer)

효율성 테스트에서 실패하여 다른 코드를 참조하여 코드를 수정했다.

이 문제의 표의 길이는 무려 1,000,000으로 리스트를 사용해서 삭제, 추가를 할 경우
200,000 * 1,000,000 이므로 효율성 테스트를 절대 통과할 수 없다.

따라서 삽입, 삭제에 O(1)이 걸리는 Linked list를 사용해야 하는데
파이썬에는 라이브러리로 구현된 구현체가 없다.

그렇다면 직접 Linked list를 구현해서 문제를 풀어야 할까?

공부로서는 좋지만 시험장에서는 좋지 않은 판단이라고 생각한다.
따라서 해당 풀이에서도 dictionary로 linked list를 흉내내서 풀었다.

{key : [ before, next ] }

위와 같이 구현되었다.

Linked list에서는 하나의 노드가 다음 노드의 포인터를 갖지만
dictionary에서는 하나의 key가 before값과 next 값을 갖는 배열의 첫번째 요소의 주솟값을 가르키고 있을 것이다.