[프로그래머스] 표 편집 (Python) - Linked List

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

프로그래머스

 

오랜만에 자료구조형에 대해 생각해 볼 수 있는 문제를 풀었당

 

문제상황 (시간 초과)

맨 첨에는 list 만들고 삭제하면 0 , 데이터 있는 값은 1 이렇게 테이블을 만들어주었다. 

그러나 list 로 테이블을 관리하게 되면.. Z 복구 연산의 경우 0 -> 1로 바꿔주는거니 O(1) 이지만, 

행들을 순차적으로 탐색해야 하는 U, D, C 연산의 경우 시간복잡도에서 걸린다. 

최대 cmd 가 200000개이고, 예를들어 선형 탐색 O(N)을 하는 U,D,C 연산만 수행하며, 테이블 행 길이가 최대 1000000 이면 연산량이 크다 (그리고 문제에서 효율성 점수가 있다고 언급했다 )

 

해결방법 

자료구조형을 연결리스트로 구현할 수 있다. 중간 중간 테이블의 데이터가 삭제되어서 칸의 이동을 해주어야 하는 경우, link로 previous node, next node를 이을 수 있다.

U, D, C연산의 시간복잡도는 O(X) 까지 줄일 수 있으며, Z 연산의 경우 O(1)에 해결할 수 있다...! 

* X 는 커서가 이동하는 노드 수이다. 리스트 자료구조는 모든 원소를 하나씩 거쳐가야 하지만, 링크드리스트는 유효한 행 (노드)들만 거쳐갈 수 있다. 

 

def solution(n, k, cmd):
    answer = ['O']*n
    
    table = {i : [i-1, i+1] for i in range(n)} # 행번호 : [prev, next]
    table[0][0] = None
    table[n-1][1] = None 
    
    buffer = []
    
    for c in cmd:
        cmd_list = c.split(' ')
        if cmd_list[0] == 'U': # up 이므로 prev <-
            m = int(cmd_list[1])
            for i in range(m): # next 만큼 이동하기 
                k = table[k][0]
                
        elif cmd_list[0] == 'D': # down 이므로 next ->
            m = int(cmd_list[1])
            for i in range(m):
                k = table[k][1]
                
        elif cmd_list[0] == 'C':
            answer[k] = 'X'
            prev, next = table[k]
            buffer.append([prev, k, next])
            
            # k 처리하기 
            if next == None:
                k = prev
            else:
                k = next
            
            # 연결해제하기 
            if prev == None: # 맨 앞 노드였음
                table[next][0] = None 
                
            elif next == None: # 맨 끝 노드
                table[prev][1] = None 
                
            else: # 일반적인 노드 
                table[next][0] = prev
                table[prev][1] = next
                
            
        else: # Z 복구 
            prev, now, next = buffer.pop()
            answer[now] = 'O' # 복구하기
            if prev == None: # now 가 맨 첫번재 노드 
                table[next][0] = now # next 값만 처리해주면 된다. 
            elif next == None:# now가 맨 마지막 노드
                table[prev][1] = now 
            else:    
                table[next][0] = now # next 의 prev는 now
                table[prev][1] = now # prev 의 next는 now 
    
    return "".join(answer)