[프로그래머스] 표편집 (파이썬)

📕 문제

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

코딩테스트 연습 - 표 편집

 

💡 풀이법

: 그냥 리스트를 사용하면 한번 움직일 때 시간 복잡도가 O(n)이지만 연결리스트를 이용하면 O(1)이다.

해당 숫자의 앞 숫자와 뒤 숫자를 담는 리스트를 값으로 하는 딕셔너리를 만든다.

1. 위, 아래로 내려가는 함수와 삭제하는 함수를 따로 만든다.

2. 삭제하게 되면 삭제하는 숫자의 answer값을 'X'로 바꾸어 주고 삭제한 숫자를 담는 z_box에 숫자를 담아준다. 그리고 삭제하려는 숫자의 앞에 있는 숫자의 뒷 숫자 값과 뒤에 있는 숫자의 앞 숫자 값이 바뀌어야한다.

-> 무슨 말 장난 같네 쉽게 예를 들어 설명해보면;;

1,2,3,4,5의 순서대로 있을때 3이 삭제되면 딕셔너리에서 키 2의 값이 [1,3] -> [1,4]로 바뀌어야하고, 키 4의 값이 [3,5] -> [2,5]로 바뀌어야 한다!

3. 삭제한 숫자를 되돌리려면 z_box에서 숫자를 pop해서 answer값을 'O'로 다시 바꿔주고, 앞 뒤 숫자의 딕셔너리 값들도 원상복귀 해준다.

-> 1,2,(3),4,5의 순서대로 있을때 3이 복구되면 딕셔너리에서 키 2의 값이 [1,4] -> [1,3]로 바뀌어야하고, 키 4의 값이 [2,5] -> [3,5]로 바뀌어야 한다!

def solution(n, k, cmd):

    def down(x, pointer):
        for _ in range(x):
            pointer = dict[pointer][1]
        return pointer

    def up(x, pointer):
        for _ in range(x):
            pointer = dict[pointer][0]
        return pointer

    def delete(pointer):
        nonlocal z_box
        a, b = dict[pointer]
        z_box.append([pointer, [a,b]])
        answer[pointer] = 'X'
        
        if a != -1:
            dict[a][1] = b

        if b != n:
            dict[b][0] = a
            pointer = dict[pointer][1]
        else:
            pointer = dict[pointer][0]

        return pointer


    answer = ['O'] * n
    dict = {}
    for i in range(n):
        dict[i] = [i-1, i+1]
    z_box = []
    for c in cmd:
        c = c.split()
        if c[0] == "D":
            k = down(int(c[1]), k)
        if c[0] == "U":
            k = up(int(c[1]), k)
        if c[0] == "C":
            k = delete(k)
        if c[0] == "Z":
            p, lst = z_box.pop()
            answer[p] = 'O'

            if lst[0] == -1:
                dict[lst[1]][0] = p
            elif lst[1] == n:
                dict[lst[0]][1] = p
            else:
                dict[lst[0]][1] = p
                dict[lst[1]][0] = p

    return ''.join(answer)