-
[링크드리스트] 표 편집 (파이썬)코딩 테스트/프로그래머스 2023. 5. 6. 18:59
문제 설명
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를 가르키고 있을 때
- 삭제 요청시
- 해당 노드가 처음이나 끝이 아니라면 노드의 왼쪽 노드는 pivot의 오른쪽 값을
- 노드의 오른쪽 노드는 pivot의 왼쪽 값을 넣어 줌.
- eg ) pivot이 2 : [1,3] 인 노드를 가르키고 있다면 gr[1][1]=3, gr[3][0] = 1
- 이 후 del 명령어로 gr[pivot] 삭제 후 , 휴지통에 넣어둠 ( [pivot, left, right ] )
- 복구 할 때 left right 값 연결을 위해 휴지통엔 pivot값과 left right 값 같이 넣어주는것
- 이후 pivot은 right값을 가르켜줌
- 해당 노드가 첫 노드라면 left 값은 없으니 신경 x
- 이 노드는 삭제 될 것이므로 다음 노드가 맨 첫 노드가 됨
- gr[right][0]= False
- 노드가 마지막 노드라면 right는 없으니 신경 ㄴㄴ
- gr[left][1]= False
- 해당 노드가 처음이나 끝이 아니라면 노드의 왼쪽 노드는 pivot의 오른쪽 값을
- 이동 규칙은 반복문을 통해 왼쪽 이나 오른쪽으로 순회 하면 됨
- 복구 명령은 삭제와 반대로 꺼내온 키 값을 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"]))
'코딩 테스트 > 프로그래머스' 카테고리의 다른 글
[파이썬] 가장 긴 팰린드롬 (파이썬) (0) 2023.05.08 [최단거리] 부대 복귀 (파이썬) (0) 2023.05.06 [파이썬] 풍선 터트리기 (0) 2023.05.03 [데브 매칭] 다단계 칫솔 판매 ( 파이썬 ) (0) 2023.04.26 [탐색] 자물쇠와 열쇠 (파이썬) (0) 2023.04.25