[링크드리스트] 표 편집 (파이썬)

문제 설명

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

프로그래머스

문제 풀이

• 주어진 규칙에 따라 위치를 이동하고, 해당 위치 요소를 삭제하거나 가장 최근에 삭제 된 요소를 복구하는 문제
• 해당 문제의 조건이 아래와 같으므로 삭제나 복구 수행시 리스트를 직접적으로 순회하며 추가 삭제를 하면 시간 초과가 됨 
  • 5 ≤ n ≤ 1,000,000
  • 0 ≤ k < n
  • 1 ≤ cmd의 원소 개수 ≤ 200,000
• 가장 빠르게 접근하기 위해 링크드 리스트를 도입
• 딕셔너리로 생성해서 각 key는 노드를, 해당 value는 [left 노드 수, right 노드 수] 를 저장 ( eg. 1 : [ 0,2 ] )
• pivot이 현재 2를 가르키고 있을 때
  • 삭제 요청시
    1. 해당 노드가 처음이나 끝이 아니라면 노드의 왼쪽 노드는 pivot의 오른쪽 값을
       1. 노드의 오른쪽 노드는 pivot의 왼쪽 값을 넣어 줌. 
       2. eg ) pivot이 2 : [1,3] 인 노드를 가르키고 있다면 gr[1][1]=3, gr[3][0] = 1 
       3. 이 후 del 명령어로 gr[pivot] 삭제 후 , 휴지통에 넣어둠 ( [pivot, left, right ] ) 
       4. 복구 할 때 left right 값 연결을 위해 휴지통엔 pivot값과 left right 값 같이 넣어주는것
       5. 이후 pivot은 right값을 가르켜줌
    2. 해당 노드가 첫 노드라면 left 값은 없으니 신경 x
       1. 이 노드는 삭제 될 것이므로 다음 노드가 맨 첫 노드가 됨
       2. gr[right][0]= False 
    3. 노드가 마지막 노드라면 right는 없으니 신경 ㄴㄴ
       1. gr[left][1]= False
  • 이동 규칙은 반복문을 통해 왼쪽 이나 오른쪽으로 순회 하면 됨
  • 복구 명령은 삭제와 반대로 꺼내온 키 값을 left와 right로 딕셔너리에 담아주고 해당 left,right 노드는 key와 연결 해주면 됨
  •  

소스코드

# D 2: x에서 2 down
# U 2:x에서 2 up
# C : x 삭제
# Z : 가장 최근 삭제 된 것들 복구 (복구 시 x가 아닌 원래 자리로 )(삭제 할 때 위치도 저장해야함)

# n <= 1,000
def solution(n, pivot, cmd):
    answer = ''
    gr = dict()
    for i in range(n):
        gr[i] = [i-1,i+1]
    gr[0][0]="False"
    gr[n-1][1]="False"
    
    garbage = []
    for c in cmd:
        if len(c)==1:
            if c == "Z":
                key,left,right = garbage.pop()
                gr[key]=[left,right]
                if left=="False":
                    gr[right][0]=key
                elif right=="False":
                    gr[left][1]=key
                else:
                    gr[left][1]=key
                    gr[right][0]=key
                
            else:
                left,right = gr[pivot]
                if left=="False":
                    gr[right][0]="False"
                    del gr[pivot]
                    garbage.append([pivot,left,right])
                    pivot=right
                elif right=="False":
                    gr[left][1]="False"
                    del gr[pivot]
                    garbage.append([pivot,left,right])
                    pivot=left
                else:
                    gr[left][1]=right
                    gr[right][0]=left
                    del gr[pivot]
                    garbage.append([pivot,left,right])
                    pivot=right
                    
        else:
            dic, move  = c.split(" ")
            move = int(move)
            if dic=="D":
                for i in range(move):
                    pivot=gr[pivot][1]
            else:
                for i in range(move):
                    pivot=gr[pivot][0]
                
    answer=["X"]*n
    for k in gr:
        answer[k]="O"
    answer= "".join(answer)
    return answer

print(solution(8,
                2,
                ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"]))
# ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"]))