LeetCode 23. Merge k Sorted Lists, k개 정렬 리스트 병합

문제 링크

 

문제 설명: k개의 정렬된 리스트를 1개의 정렬된 리스트로 병합하라.

원문설명: You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

 

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

 

1. 처음 접근했던 방법에 대한 설명 (완료되지 않은 풀이이며, 최적화가 되지 않았음)
   1. ListNode를 생성하고 해당 node에 조건에 맞춰 node들을 이어 붙임.
   2. 반복문 안에서 가장 작은 값을 판별함.
      min = last[i].val;
   3. 가장 작은 값을 지닌 node를 next로 넘김
      lists[ptr] = lists[ptr].next;
   4. 판별된 값으로 새로운 node를 생성하고 답변이 될 node에 이어붙임.
      node.next = new ListNode(min);
   5. lists에 있는 모든 node가 null이 될 시 반복문을 벗어남.

public class MergeKSortedLists {
    public ListNode mergeKLists(ListNode[] lists) {
        int k = lists.length;
        ListNode node = new ListNode(0);
        ListNode head = node;
        boolean isDone = false;

        while (true) {
            int i = 0; // 각 노드를 순회할 때 인덱스로 사용할 변수
            int ptr = 0; // 가장 작은값을 가지고 있는 노드의 인덱스
            int min = 10000; // 문제에서의 제약 조건인 수의 크기 10 ^ 4
            int nullCounter = 0;

            for (; i < k; i++) {
                if (lists[i] != null) {
                    if (min > lists[i].val) {
                        // 가장 작은 수 판별 및 값 대입
                        min = lists[i].val;
                        ptr = i;
                    }
                } else {
                    nullCounter++;
                    // lists에 담겨있는 node를 순회하는 중 해당 node가 null이 된 경우를 셈
                    // 모든 node가 null이 되면 isDone을 true로 대입
                    isDone = nullCounter == k;
                }
            }

            // for문 순회 중 가장 작은수를 가지고 있던 node를 다음으로 넘김
            if (lists[ptr] != null) {
                lists[ptr] = lists[ptr].next;
            }

            // 가장 작은 값을 새로운 node로 생성한 후 답변이 될 node에 이어붙임
            node.next = new ListNode(min);
            node = node.next;

            if (isDone) break;
        }

        return head.next;
    }
}

 

 

2. O(n) 풀이법

• PriorityQueue를 사용하여 'ListNode[]' 에 담겨있는 head 값들을 전부 추가한다.
• 답이 될 ListNode 를 새로 선언한다.
  • queue에 담겨있는 node들을 next로 넘겨주며 선언한 node에 연결해준다.

public ListNode mergeKListsB(ListNode[] nodes) {
        ListNode tmpNode = new ListNode(0);
        ListNode answer = tmpNode;
        
        // lists에 있는 node들의 value를 비교하는 우선순위 큐
        PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.val));

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

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

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

        return answer.next;
    }

 

이 문제를 O(n)에 풀이하는데 가장 중요한 요소는 두가지다.

1. 값의 비교

2. 값이 정렬된 노드의 생성

 

값의 비교는 PriorityQueue를 통해 한다.

new PriorityQueue<>(Comparator.comparingInt(n -> n.val)) 코드를 통해 우선순위 비교 구현은 완료된다.

 

정렬된 리스트는 pq에서 값을 추출하고 추가하기를 반복하며 생성한다.

 if (tmpNode.next != null) pq.add(tmpNode.next);

pq에 있는 node들을 poll() 했을 시, pq는 해당 node가 없어진다.
{head1, head2, head3} 와 같이 있을 경우 head1이 poll() 되면, {head2, head3} 이 되는 것이다.
tmpNode의 값을 다시 우선순위 큐에 추가하며 {head2, head3, head1's next}이 된다.

이 작업을 반복하며 정렬된 ListNode를 만든다.