10주차. 데크, 우선순위(k개 정렬 리스트 병합)

27. k개 정렬 리스트 병합

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

Merge k Sorted Lists - LeetCode

📌문제

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

- 예제1
  📝입력

Input: lists = [[1,4,5],[1,3,4],[2,6]]

  💻출력

Output: [1,1,2,3,4,4,5,6]

    
📌풀이

5ms, 44.3mb

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<Integer> q = new PriorityQueue<>();
        for(ListNode node : lists) {
            while (node != null) {
                q.add(node.val);
                node = node.next;
            }
        }
        ListNode answer = null;
        ListNode temp = null;
        while(!q.isEmpty()){
            if(answer == null){
                temp = new ListNode(q.poll());
                answer = temp;
            }
            else{
                temp.next = new ListNode(q.poll());
                temp = temp.next;
            }
        }

        return answer;
    }
}

우선순위 큐를 사용한다면 어렵지 않은 문제다. 그대로 ListNode에 넣어주면 된다. 근데 이게 왜 hard...?