[PG/Python] 표 편집

📌 문제

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

코딩테스트 연습 - 표 편집

 

📌 문제 접근 방법

1. 연결리스트를 활용하여 삽입, 삭제의 시간 복잡도를 O(1)으로 구현하였다.
   표에서 초기 행 번호를 key, 해당 번호의 앞/뒤 행 번호를 리스트 형태로 value에 저장했다.
2. 인덱스의 이동의 경우, x번만큼 위/아래로 이동하도록 하였다.
3. 삽입, 삭제의 경우, 첫 번째 인덱스일 경우/마지막 인덱스일 경우/그 외의 경우를 나누어서 인덱스를 변경시켰다.

 

📌 코드

def solution(n, k, cmd):
    table = {x : [x-1, x+1] for x in range(n)}
    answer = ['O' for _ in range(n)]
    deleted = []
    
    for c in cmd:
        if len(c) > 1:
            c, x = c.split()
        
        if c == 'U':
            for _ in range(int(x)):
                k = table[k][0]
        elif c == 'D':
            for _ in range(int(x)):
                k = table[k][1]
        elif c == 'C':
            before, after = table[k]
            deleted.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 = deleted.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
            
    return ''.join(answer)