[코드트리/파이썬] 가로등 설치 - 2

Codetree | Learning to Code with Confidence

코딩테스트 기출 문제 설명: 가로등 설치 | 코드트리

 

double linked list, heap의 Lazy Deletion을 활용해서 빠른 시간에 가로등 ID와 위치를 찾아내고 제거 처리를 할 수 있을 것이냐.

추가로, 바로바로 삭제 처리를 하면 시간 복잡도가 초과할 수 있기 때문에 지연 처리, Lazy Deletion을 할 수 있느냐 를 물어보는 문제.

코딩테스트 연습 - 이중우선순위큐

프로그래머스

 

관련 문제로 프로그래머스 이중우선순위큐 문제가 Lazy Deletion 문제로 소개되고 있다.

https://github.com/jeongminllee/CodeTreeTest/blob/main/samsung-sw/%EA%B0%80%EB%A1%9C%EB%93%B1%20%EC%84%A4%EC%B9%98/street-light-installation.py

CodeTreeTest/samsung-sw/가로등 설치/street-light-installation.py at main · jeongminllee/CodeTreeTest

처음에 좀 헤맸는데 스터디 끝에 풀 수 있게 되었다. 그러나 또 이런 문제 만나면 고전하겠지? 분석 좀 더하자. 

마을 초기 환경 설정 할때 링크드 리스트와 힙을 어떻게 구현할 것인가를 조금 더 세밀히 공부할 필요가 있다. 제한 조건을 보면 일단 단순하게 방문을 통해서 모든 처리를 하기에는 조건의 수가 많다. 그 말은 시간복잡도 측면에서 모든 처리를 일반적인 배열에 처리를 하게 되면 무조건 초과가 날 것이기 때문에 아까 풀이한 대로 가장 긴 도로의 길이만 추려서 계산하면 된다.

그러면 우리가 고민해봐야할 길이는 [시작점 - 가장 왼쪽 가로등 / 가장 오른쪽 가로등 - 종료점 / 각 가로등 사이의 거리] 이정도가 되겠는데 나는 처음에 이 거리들을 한 곳에 모아서 관리를 하려고 했다. 그러나 그럴 필요가 없는 것이, 시작점과 종료점에 해당하는 거리는 이중 링크드 리스트와 우선순위 큐로 관리를 하고, 각 가로등 사이의 거리 중 가장 긴 거리는 우선순위 큐로 관리를 하면 복잡하게 고민하지 않아도 각각의 자료구조에 따라 하나씩만 가져오면 된다. 

우선 시작점과 연관있는 가로등은 가장 왼편에 있는 가로등. 왼쪽을 바라보는 링크드 리스트와 위치값과 ID 값을 담은 최소힙으로 관리를 한다. 종료점과 연관있는 가로등 역시 가장 오른편에 있는 가로등이기 때문에 오른쪽을 바라보는 링크드리스트와 위치값과 ID 값을 담은 최대힙으로 관리를 한다. 

가로등 사이에 있는 거리는 객체로 해서 왼편 가로등, 오른편 가로등, 거리, 시작점 등을 담아 관리를 하고 이를 힙으로 역시 관리를 한다. 이때 길이가 긴 순서대로 정렬을 해 루트 부분에 길이가 가장 긴 객체가 오게 한다. 사실 이 부분이 제일 이해가 안 됐는데 직접 print를 찍어서 보니까 heap인데도 불구하고 정렬이 되는 모습이 좀 신기했다. 

추가는 어떻게 할까. 가로등 추가가 되면, 가장 긴 두 가로등 사이의 도로는 작은 두 개의 도로로 갈라지면서 1개가 사라지고 2개가 생성된다고 할 수 있다. 이때 생성된 가로등은 왼쪽 - 생성, 생성 - 오른쪽 으로 구분되어 도로를 형성하고, 이 부분을 각각 링크드 리스트와 위치값을 담고 있는 힙, 거리를 담고 있는 힙에 저장하면 된다.

반대로 삭제의 경우는 두 개의 도로가 사라지고 하나의 새로운 도로가 생기는 것이다. 삭제는 추가와 다르게 가장 왼편, 가장 오른편에 있는 가로등도 삭제가 되기 때문에 이 부분에서 조금 예민하게 다룰 필요가 있다. 만약 시작점과 종료점에 맞닿아 있는 가로등이라면 거리 힙에는 추가하지 않고 링크드리스트만 조정을 주고, 아니라면 거리 힙을 조정한다. 

지금까지는 힙에 저장되어 있던 것들을 삭제처리 하지 않고 삭제 체크만하고 있었는데 언제 삭제할 것이냐. 가장 긴 도로를 구할 때 삭제 처리를 할 것이다. 가장 긴 거리를 요구하는 부분은 추가하는 부분과 최적의 전력을 계산하여 출력하라는 명령 부분이기 때문에 이 두 명령어가 떨어지면 그때 한번씩 기존에 삭제 체크를 했었던 부분을 한 번 정리한다는 느낌?으로 가져갔으면 좋겠다. 따라서 추가 하는 부분에서는 명령이 떨어지면 가로등 사이의 가장 긴 도로를 구해야 하기 때문에 삭제처리가 이루어지고, 가로등 추가하는 단계에서는 삭제 체크만 이루어지게 된다.

이러한 부분을 잘 생각하면 쉽게 정답을 구할 수 있을 것이다.