[LeetCode] 23. Merge k Sorted Lists (Java, C++)

문제

 

https://leetcode.com/problems/merge-k-sorted-lists/

Merge k Sorted Lists - LeetCode

 

풀이

 

난이도: Hard

 

대표적인 우선순위 큐 문제.

 

일반적인 정렬로 해결하기에는 범위가 너무 크다.

리스트의 최대 개수(k)는 10,000개, 각 리스트의 연결 노드들은 최대 500개가 될 수 있다.

모두 한꺼번에 정렬로 해결할려면 최악의 경우 5,000,000 개의 노드를 정렬해야 하므로 정렬의 시간 복잡도 O(n log n) 으로는 시간 초과가 발생할 수 있다.

 

따라서 한꺼번에 모든 노드를 정렬하기 보다는 각 리스트에서 단계적으로 값을 가져와 정렬을 해야 한다.

이 처럼 삽입 삭제가 잦은 경우 효율적인 자료구조가 바로 우선순위 큐(Priority Queue)이다.

 

우선순위 큐는 삽입과 삭제를 O(log n)의 복잡도로 해결이 가능하고, 무엇보다 정렬의 기준에 따라 가장 우선순위가 높은 값을 순서대로 저장하고 있다. 따라서 작은 순서 대로 정렬했다면 큐의 가장 위의 값에서 순서대로 꺼내오면 정렬된 순서를 알 수 있다.

 

이번 문제에 적용해서 시간 복잡도를 계산해 보자.

일단 각 리스트들의 가장 앞의 노드를 우선순위 큐에 삽입해 정렬한다.

(모든 리스트들은 이미 정렬되어 있기 때문에 가장 앞의 노드가 그 리스트의 최소 값을 가진다.)

이제 우선 순위 큐의 노드를 하나씩 꺼내오고 해당 노드의 다음 노드를 우선순위에 삽입한다.

이러면 항상 우선순위 큐의 크기는 lists의 개수(k = 10,000) 이하로 유지된다.

따라서 우선순위 큐의 삽입과 삭제 복잡도는 O(log k)가 되며, 모든 노드가 한 번씩은 삽입, 삭제가 되므로 총 시간 복잡도는 O(2*n log k)가 된다. k가 n보다 훨씬 작기 때문에 O(n log n)보다는 빠른 속도를 기대할 수 있다.

 

 

자바에서 사용자가 정의한 클래스를 우선순위 큐로 정렬하려면 Comparable인터페이스를 상속하여 compareTo()를 구현하거나, Comparator 클래스의 compare()를 오버라이딩 해야 한다.

 

둘의 차이를 살펴보자.

Comparable을 상속하면 해당 클래스와 다른 클래스를 비교하는 compareTo() 함수를 구현해야 한다.

이 함수는 매개변수가 하나이기 때문에 호출한 객체.compareTo()와 매개변수로 넘어온 값을 비교한다.

 

Comparator 클래스의 compare()함수는 매개변수가 넘어온 두 개로 두 값을 비교한 결과를 반환한다.

 

이번 문제는 이미 구현된 ListNode를 이용하는 것이므로 익명 클래스로 구현한 compare함수 사용하였다.

 

코드

 

JAVA

 

 

C++