/leetcode23/ Merge k Sorted Lists

k 개의 정렬된 연결 리스트를 병합하여 하나의 정렬된 리스트로 만드는 문제이다.

C++ STL의 priority_queue를 이용한 풀이를 통해, 우선순위 큐의 사용방식을 이해해본다.

https://leetcode.com/problems/merge-k-sorted-lists/discuss/458432/C%2B%2B-20ms-beat-98.78-and-Python-84ms-beat-99.50

 

ListNode 구조체의 val 값을 비교하므로 < 연산자를 오버로딩하거나 

bool operator( )를 갖는 구조체나 클래스를 정의해서 사용해야 한다.

 

priority_queue의 정의는

priority_queue <자료형, 컨테이너 구현체, 비교 연산자> 방식으로 한다.

컨테이너는 기본설정과 동일한 vector컨테이너로 지정하였다.

 

우선 k 개의 벡터를 모두 우선순위 큐에 삽입하고

ListNode 포인터 cur을 옮겨가는 방식으로 구현되었다.