LeetCode - The World's Leading Online Programming Learning Platform

Problem

1. input: 연결리스트가 든 배열 lists
2. output: 배열의 연결리스트들을 하나의 정렬된 연결리스트로 만들어 리턴

• k == lists.length
• 0 <= k <= 104
• 0 <= lists[i].length <= 500
• 104 <= lists[i][j] <= 104
• lists[i] is sorted in ascending order.
• The sum of lists[i].length will not exceed 104

Idea

해당 문제는 주어진 배열을 정렬하는 문제이다.

여러가지 정렬 방법 중 간편하고 빠른 것으로 퀵, 힙, 병합 정렬을 떠올렸다.

이미 연결리스트가 정렬된 상태로 나누어져 존재하기 때문에 병합정렬을 사용하고자 했다.

Solution

1. 모든 연결리스트에 대해 동시에 병합 정렬

   이미 각 연결리스트는 정렬이 된 상태로 얼추 나누어진 상태 → 병합 정렬

   각 연결리스트의 첫번째 원소를 동시에 비교하여 가장 작은 값부터 삽입하는 방식

   class Solution {
       fun mergeKLists(lists: Array<ListNode?>): ListNode? {
           val listNodes = lists.toMutableList()
           val answer = ListNode(0)
           var cursor = answer
           while (true) {
               var min = 10001
               var minIdx = -1
   						// 각 연결리스트의 head 원소 중 최솟값 찾기
               for (i in lists.indices) {
                   if (lists[i] != null && lists[i]!!.`val` < min) {
                       minIdx = i
                       min = lists[i]!!.`val`
                   }
               }
               if(minIdx == -1) break // 모든 연결리스트가 병합된 경우
   						// 최솟값 정답에 삽입
               cursor.next = lists[minIdx]!!
               cursor = cursor.next!!
               lists[minIdx] = lists[minIdx]!!.next
           }
           return answer.next
       }
   }
   

   시간 복잡도: 배열 순회(각 연결 리스트의 최솟값 찾기)n X 연결 리스트 순회(각 원소)m = nm

   (n: lists안의 연결리스트 수, m: 전체 숫자 수)

   

   🚫⁉

   • 최악의 경우 병합이 원소의 전체 갯수 만큼 일어나므로 병합 정렬(분할 정복)X
   • 최솟값이 아닌 원소들은 계속해서 다시 비교해야함

2. 연결 리스트를 2개씩 병합 정렬 (1의 2번째 문제 해결)

   첫번째 연결리스트를 고정하고 나머지 연결리스트를 한개씩 병합 정렬

   class Solution {
       fun mergeKLists(lists: Array<ListNode?>): ListNode? {
           val listNodes = lists.toMutableList()
           var answer: ListNode? = null
           var cursor = answer
   				// 연결리스트를 2개씩 병합 정렬
           for (list in lists) {
               answer = mergeTwoList(answer, list)
           }
           return answer
       }
   		// 2개의 연결리스트를 병합 정렬
       fun mergeTwoList(listNode1: ListNode?, listNode2: ListNode?): ListNode? {
           var l1 = listNode1
           var l2 = listNode2
           var start = ListNode(0)
           var cursor = start
           while (true) {
               if (l1 == null) { // 한쪽이 다 비워진 경우
                   cursor.next = l2
                   break
               } else if (l2 == null) { // 한쪽이 다 비워진 경우
                   cursor.next = l1
                   break
               } else { // 둘 중 작은 원소 삽입
                   if (l1.`val` <= l2.`val`) {
                       cursor.next = l1
                       cursor = cursor.next!!
                       l1 = l1.next
                   } else {
                       cursor.next = l2
                       cursor = cursor.next!!
                       l2 = l2.next
                   }
               }
           }
           return start.next
       }
   }
   

   시간 복잡도: 배열 순회(각 연결 리스트)n X 연결 리스트 순회(정렬)m = nm

   (n: lists안의 연결리스트 수, m: 전체 숫자 수)

   

   🚫⁉

   • 하나의 리스트를 고정하기 때문에 병합 정렬(분할 정복)X

3. 연결리스트 2개씩 분할정복 (2의 문제 해결)

   병합 정렬의 성능적 이점은 병합이 n번이 아닌 log n이라는 것이므로, 2개씩 분할 정복해야함

   (병합 정렬은 분할이 될때 항상 반으로 나누어져야 하기 때문에, 엄밀히 병합 정렬은 아님)

   2와 병합부분은 동일

   class Solution {
       fun mergeKLists(lists: Array<ListNode?>): ListNode? {
           if (lists.isEmpty()) return null
           if (lists.size == 1) return lists.first()
           var length = lists.size
           var gap = 1
           // 두개씩 짝지어 merge
           while (gap <= length / 2) { log n
               for (i in 0..(length - gap * 2) step gap * 2) { (n) n
                   lists[i] = mergeTwoList(lists[i], lists[i + gap])
                   lists[i + gap] = null
               }
               if ((length / gap) % 2 == 1) { // 남은 갯수가 홀수인 경우 처음과 끝 merge
                   lists[0] = mergeTwoList(lists[0], lists[((length / gap) - 1) * gap])
                   lists[((length / gap) - 1) * gap] = null
               }
               gap *= 2
           }
           return lists[0]
       }
       
       // 병합 정렬
       fun mergeTwoList(listNode1: ListNode?, listNode2: ListNode?): ListNode? {
           var l1 = listNode1
           var l2 = listNode2
           var start = ListNode(0)
           var cursor = start
           while (true) {
               // 한쪽의 원소가 더이상 없는 경우
               if (l1 == null) {
                   cursor.next = l2
                   break
               } else if (l2 == null) {
                   cursor.next = l1
                   break
               } else { // 양쪽에서 더 작은 거 찾아서 삽입
                   if (l1.`val` <= l2.`val`) {
                       cursor.next = l1
                       cursor = cursor.next!!
                       l1 = l1.next
                   } else {
                       cursor.next = l2
                       cursor = cursor.next!!
                       l2 = l2.next
                   }
               }
           }
           return start.next
       }
   }
   

   시간 복잡도: 배열 2개씩 병합 log n X 연결 리스트 순회(정렬)m = m log n

   

Point

1. 병합 정렬