23. Merge k Sorted Lists - Streak 10

하드 치고는 간단한 우선순위 큐 문제였다.

우선순위 큐를 이용해 매 순간 바로 뒤에 와야 할 노드를 찾아 추가해주었다.

약간 까다로운 점은 우선순위 큐에 담을 자료구조였는데, record를 하나 만들고 그 안에 Comparable을 구현해서 해결하였다.

/**
 * 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 {
    PriorityQueue<Pair> pq = new PriorityQueue<>();
    public ListNode mergeKLists(ListNode[] lists) {
        int k = lists.length;
        ListNode head = new ListNode(0);
        ListNode tail = head;
        for(int i = 0; i<k; i++){
            if(lists[i] == null) continue;
            pq.add(new Pair(lists[i].val, i));
        }
        while(!pq.isEmpty()){
            Pair nowPair = pq.poll();
            tail.next = new ListNode(nowPair.first());
            tail = tail.next;
            lists[nowPair.second()] = lists[nowPair.second()].next;
            if(lists[nowPair.second()] != null){
                pq.add(new Pair(lists[nowPair.second()].val, nowPair.second()));
            }
        }
        return head.next;
    }
}



record Pair(Integer first, Integer second) implements Comparable<Pair>{
    @Override
    public int compareTo(Pair o) {
        int cmp = first.compareTo(o.first);
        if (cmp != 0) return cmp;
        return second.compareTo(o.second);
    }
}