[자바 알고리즘 인터뷰] 10장 데크, 우선순위 큐 (2) k개 정렬 리스트 병합

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

 

- k개의 정렬된 리스트를 1개의 정렬된 리스트로 병합하라 

 

 

풀이 1) 우선순위 큐를 이용한 리스트 병합 

 

우선순위 큐 

 

- 어떠한 특정 조건에 따라 우선순위가 가장 높은 엘리먼트가 먼저 추출되는 자료형

 

- 이 문제의 예제 입력값은 [[1,4,5],[1,3,4],[2,7]] 이며, 먼저 다음과 같이 반복문으로 각 연결 리스트의 첫 번째 노드를 큐에 저장한다. 

//각 연결 리스트의 첫 번째 노드를 큐에 저장
for(ListNode node : lists)
{
    if(node!=null)
        pq.add(node);
}

 

- 이렇게 하면 큐에는 각 연결 리스트의 루트인 1,1,2가 저장된다. 

- 그렇다면 이 중에서 가장 작은 값을 지닌 노드를 끄집어내고 그 다음 노드를 다시 큐에 넣어주는 식으로 반복한다. 

 

//큐가 모두 빌 때까지 반복
while(!pq.isEmpty()) {
    //우선 순위에 따라 추출, 다음 노드로 이동
    tail.next = pq.poll();
    tail = tail.next;

    //추출한 연결 리스트의 다음 노드는 다시 큐에 저장
    if(tail.next!=null)
        pq.add(tail.next);
}

 

 

- 이렇게 큐가 빌 때까지 반복하면서 우선순위에 따라 가장 작은 값을 지닌 노드를 추출하고 그 노드의 다음 노드인 tail.next를 다시 큐에 집어 넣으면 큐와 tail 연결 리스트는 다음과 같이 진행된다. 

 

출처 : 자바 알고리즘 인터뷰 with 코틀린 저자: 박상길 <책만>

 

 

- PriorityQueue는 compare() 메소드로 정의한 순서에 따른 우선순위 큐가 된다. 

- 여기서 기준은 val의 값이 작을수록 더 작은 값을 갖기 때문에 결국 우선순위 큐는 값이 작은 순으로 추출될 것이다. 

 

public ListNode mergeKLists(ListNode[] lists) {
 PriorityQueue<ListNode> pq = new PriorityQueue<>((o1,o2)-> {
     //동일한 값이면 무시
     if(o1.val==o2.val)
         return 0;
     //새로운 값(o1)이 기본 값(o2)보다 크면 뒤에 위치
     else if(o1.val>o2.val)
         return 1;
     else
         return -1;
 });

 

 

 

 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>((o1,o2)-> {
            //동일한 값이면 무시
            if(o1.val==o2.val)
                return 0;
            //새로운 값(o1)이 기본 값(o2)보다 크면 뒤에 위치
            else if(o1.val>o2.val)
                return 1;
            else
                return -1;
        });

        ListNode root = new ListNode(0);
        ListNode tail = root;

        //각 연결 리스트의 첫 번째 노드를 큐에 저장
        for(ListNode node : lists)
        {
            if(node!=null)
                pq.add(node);
        }

        //큐가 모두 빌 때까지 반복
        while(!pq.isEmpty()) {
            //우선 순위에 따라 추출, 다음 노드로 이동
            tail.next = pq.poll();
            tail = tail.next;

            //추출한 연결 리스트의 다음 노드는 다시 큐에 저장
            if(tail.next!=null)
                pq.add(tail.next);
        }

        return root.next;
    }
}

4밀리초