ch10-2(leetcode 23). k개 정렬 리스트 병합

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

 

leetcode 23번 ( https://leetcode.com/problems/merge-k-sorted-lists/ )

 

풀이

교재의 방법처럼 우선순위 큐(priority queue)를 사용하면 쉽게 풀 수 있는 문제다. 

기존의 큐는 먼저 추가된 원소를 먼저 반환하는 FIFO 구조였다면, 우선순위 큐는 큐 안의 원소를 특정한 우선순위에 따라서 정렬한 뒤 우선순위가 가장 높은 원소를 반환한다. 

 

priority queue vs heapq

파이썬에서도 우선순위 큐를 지원하는 모듈이 있다. 그러나 교재에서는 heapq 모듈을 사용해서 진행했다.

실제로 우선순위 큐를 구현할 때는 힙(heap)을 주로 사용하고, 파이썬의 우선순위 큐 구현 코드를 보면 heapq 모듈을 사용하고 있다고 하므로 기능의 차이는 없다. 

 

다만 priority queue 모듈은 thread-safe인 반면 heapq는 thread-safe가 아니다. thread-safe란 멀티 스레드 환경에서 각 스레드에서 사용하는 변수의 값이 다른 스레드에 의해 변경되지 않는 것을 의미한다. 

그럼 thread-safe를 지원하는 priority queue가 더 좋은 것이 아니야? 라고 생각할 수 있지만, thread-safe를 지원하기 위해서는 내부적으로 락킹(locking)을 지원해야 한다. 추가적인 기능을 제공하기 위해서 오버헤드가 발생할 수 있고, 코딩 테스트는 멀티 스레드(multi-thread) 환경에서 실행하지 않으므로 priority queue 모듈을 사용할 필요가 없는 것이다. 

 

Locking이란, 멀티 스레드 환경에서 여러 개의 스레드가 동시에 한 변수에 접근하는 것을 막는 것이다. 그래야만 한 스레드가 어떤 변수를 사용 중일 때 다른 스레드의 개입으로 해당 변수의 값이 바뀌지 않는다. 

 

heap

힙은 또 다른 자료형(ADT)이며 리스트나 연결 리스트 등 다양한 자료형으로 구현할 수 있지만 보통은 리스트로 구현하는 듯 하다. 

힙은 min heap과 max heap이 있고, min heap의 경우 부모 노드(parent)는 자식 노드(children)보다 작거나 같은 key 값을 갖는 게 특징이며, 이를 heap property라고 한다. 그 외에는 다른 자료구조처럼 노드를 추가나 삭제하는 것은 똑같다. 노드를 하나 삭제나 추가할 때마다 heap property를 위반하지 않도록 필요 시 부모 노드와 자식 노드의 값을 바꾸는 등의 정렬 작업을 한다. 

 

알고리즘

어쨋든 풀이에서는 힙 자료형을 사용하면 문제를 쉽게 풀 수 있다고 한다. 어떻게 가능할까?

힙에 heappush()로 여러 값을 넣으면 자동으로 정렬을 해 준다. 이후 heappop()로 가장 우선순위가 낮은(여기서는 값이 작은) 원소를 리턴할 수 있다. 

for i in range(len(lists)):
	heapq.heappush(lists[i].val)

 

다만 힙에서는 값이 연결 리스트의 노드 형식이 아니라 숫자 형식으로 되어 있으므로 연결 리스트 형식으로 바꿔주는 작업도 필요하다. 

새 연결 리스트 노드를 만든 뒤 next 포인터로 새로 만든 노드(ListNode(value))를 가리키게 하고, 포인터를 뒤로 한 칸씩 이동하면 된다. 

 

heap: key 중복

다만 heapq 라이브러리에서 구현한 힙은 중복 key 값을 허용하지 않는다. 문제의 예제에서는 값이 '1'로 중복되는 경우가 있어서 오류가 발생한다. 

이 경우 값을 가공하지 않은 채 숫자 형태로 넣지 말고, tuple 형태로 가공해서 0번째 인덱스에는 노드의 값을 넣고, 1번째 인덱스에는 해당 노드가 속한 연결 리스트가 input lists 중 몇 번째 인덱스인지를 입력해 주자. 그렇게 하면 설령 0번째 인덱스인 노드의 값이 서로 겹치더라도 그 다음 1번째 인덱스로 값을 구분해서 중복 오류가 나지 않는다. 물론 실제로 1번째 인덱스 값은 사용하지 않지만 말이다. 

 

heap: node.next

아까 for loop를 돌면서 lists의 i번째 인덱스를 넣었었다. 그런데 lists[i].val은 연결 리스트에 있는 모든 노드의 값이 아니라 연결 리스트의 첫 번째 노드의 값이다. 그래서 이 상태는 아직 그 다음 노드들의 값이 정렬되지 않은 상태이다. 

 

우선 각 연결 리스트의 첫 번째 노드들만 힙에 넣고, heappop()으로 가장 값이 작은 노드 하나를 리턴한다. 그리고 연결 리스트의 다음 노드를 다시 힙에 넣는다. 

 

맨 처음이 이런 상황이다. 현재 a 연결 리스트를 대상으로 정렬 작업을 하고 있다고 가정하면, 그 다음 상태는 이렇게 된다. 

 

이 방법이 가능한 이유는 각 연결 리스트(a, b, c)는 정렬이 된 상황이기 때문이다. 만약 그렇지 않았다면 모든 연결리스트의 모든 노드를 힙에 넣은 뒤 정렬을 해야 했을 것이다. 

 

 

참고한 포스트

https://docs.python.org/3/library/heapq.html

https://github.com/python/cpython/blob/main/Lib/heapq.py