[LeetCode] 23. Merge K Sorted Lists 최적 풀이 (Java)

✔️ 오늘의 리트코드 공부 기록 – Merge K Sorted Lists 

---

 

문제 요약 (Merge K Sorted Lists)

정렬된 K개의 연결 리스트가 주어질 때,이들을 하나의 정렬된 리스트로 병합하는 문제

 

문제링크: https://leetcode.com/problems/merge-k-sorted-lists

---

처음 접근 방식 (직관적인 생각)

문제를 처음 보면 이렇게 생각했다.

• “이미 각 리스트는 정렬되어 있으니까 두 개씩 합치면 되지 않을까?”

그래서 가장 먼저 떠올린 방법은 순차 병합(Sequential Merge) 이었다.

 

✔️ 순차 병합 (Sequential Merge)

1. 첫 번째 리스트와 두 번째 리스트를 병합
2. 그 결과를 세 번째 리스트와 병합
3. 이 과정을 끝까지 반복

(((L1 + L2) + L3) + L4) + ...

 

이미 mergeTwoLists 라는 함수도 이 문제에서 풀었으므로 구현 자체는 어렵지 않다.

---

코드

class Solution {

  public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) {
      return null;
    }

    for (int i = 0; i < lists.length - 1; i++) {
      lists[i + 1] = mergeTwoLists(lists[i], lists[i + 1]);
    }

    return lists[lists.length - 1];
  }


  private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;

    while (l1 != null && l2 != null) {
      if (l1.val < l2.val) {
        current.next = l1;
        l1 = l1.next;
      } else {
        current.next = l2;
        l2 = l2.next;
      }
      current = current.next;
    }

    if (l1 != null) {
      current.next = l1;
    }
    if (l2 != null) {
      current.next = l2;
    }

    return dummy.next;
  }

}

---

 

그런데… 겉보기엔 맞는 풀이 같지만, 시간이 오래걸렸다. 

 

🔹 시간 복잡도 분석

• 전체 노드 수: N
• 리스트 개수: K

순차 병합의 문제점은 이 부분이다.

• 첫 merge: 작은 리스트 + 작은 리스트
• 다음 merge: 이미 커진 결과 + 새 리스트
• 그 다음: 더 커진 결과 + 새 리스트
• …

👉 앞에서 만들어진 리스트의 노드들이 계속해서 다시 병합에 참여한다

 

결과적으로 어떤 노드는 최대 K번 가까이 다시 처리된다

• 시간 복잡도: O(N × K)

 

---

💡 핵심 아이디어

 

“왜 순차 병합은 느릴까?” → 같은 노드를 여러 번 다시 병합하기 때문
“그럼 같은 노드를 덜 다시 보게 만들 수는 없을까?”

 

 

🔗 병합 구조를 다시 설계해보자

“한쪽 리스트만 계속 키우지 말고,
항상 비슷한 크기의 리스트끼리 병합하자.” 

 

리스트를 이런 식으로 병합하면 어떨까?

L1 L2 L3 L4 L5 L6 L7 L8
↓
(L1+L2) (L3+L4) (L5+L6) (L7+L8)
↓
(R1+R2) (R3+R4)
↓
Final

 

이렇게 하면,

• 어떤 노드도
• 한 레벨에서 딱 한 번만 병합에 참여하고
• 다음 레벨로 올라갈 뿐이다.

---

 

이 구조를 보고 나서야 자연스럽게 연결된다.

“아, 이거 Merge Sort에서 봤던 구조랑 똑같네?”

 

즉,

• Divide: 리스트를 반으로 나누고
• Conquer: 각각 병합한 뒤
• Combine: 그 결과를 다시 병합하는 방식

👉 Divide & Conquer 패턴이다.

 

⏱ 시간 복잡도 분석

• 전체 노드 수: N
• 리스트 개수: K
• 레벨 수: log K
• 각 레벨에서 모든 노드를 한 번씩만 처리

👉 총 시간 복잡도: O(N log K)

 

이는

• 순차 병합의 O(NK) 대비
• 훨씬 효율적인 개선이다.

---

 

코드 (Java – Divide & Conquer)

 

class Solution {

  public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) {
      return null;
    }

    return mergeKListsDivideAndConquer(lists, 0, lists.length - 1);
  }

  private ListNode mergeKListsDivideAndConquer(ListNode[] lists, int left, int right) {
    if (left == right) {
      return lists[left];
    }
    int mid = left + (right - left) / 2;
    ListNode l1 = mergeKListsDivideAndConquer(lists, left, mid);
    ListNode l2 = mergeKListsDivideAndConquer(lists, mid + 1, right);
    return mergeTwoLists(l1, l2);
  }

  private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;

    while (l1 != null && l2 != null) {
      if (l1.val < l2.val) {
        current.next = l1;
        l1 = l1.next;
      } else {
        current.next = l2;
        l2 = l2.next;
      }
      current = current.next;
    }

    if (l1 != null) {
      current.next = l1;
    }
    if (l2 != null) {
      current.next = l2;
    }

    return dummy.next;
  }

}

 

 

📈 Time / Space Complexity

• 시간: O(N log K)  
• 공간: O(log K) (재귀 스택)

---

 

📝 이번 문제에서 얻은 깨달음

• 문제는 병합 자체가 아니라 병합 순서
• 같은 노드를 얼마나 자주 다시 보느냐가 성능을 결정
• Divide & Conquer는
  👉 단순한 최적화가 아니라 사고 구조의 전환
• 알고리즘 문제에서
  👉 Merge Sort 패턴은 정말 자주 재활용된다

---

🔹 또 다른 접근: PriorityQueue (Min Heap)

이 문제는 완전히 다른 관점으로도 풀 수 있다.

“최종 결과는 전체 노드 중에서 가장 작은 값부터 하나씩 이어 붙인 리스트다.”

 

각 리스트는 이미 정렬되어 있으므로
각 리스트의 head가 최소 후보가 된다.

 

즉, 매 순간 최대 K개의 후보 중 최소값만 고르면 된다.

 

여기서 자연스럽게 떠오르는 자료구조가 PriorityQueue (Min Heap) 이다.

---

💡 알고리즘 아이디어

1. 각 리스트의 head를 PriorityQueue에 넣는다
2. PQ에서 가장 작은 노드를 꺼내 결과 리스트에 연결
3. 꺼낸 노드의 next가 있으면 다시 PQ에 넣는다
4. PQ가 빌 때까지 반복

👉 항상 “다음으로 올 수 있는 최소 후보”만 관리하는 방식이다.

---

Divide & Conquer vs PriorityQueue

 

• Divide & Conquer: 같은 노드를 덜 보자 (병합 순서 최적화)
• PriorityQueue: 지금 가장 작은 값만 보자 (최소값 선택)

---

 

🔹 참고 - 순차 병합, Divde & Conquer, PriorityQueue 방식 비교

시간 복잡도특징

 

순차 병합	O(N * K)	매번 누적 리스트 병합 → 리스트 길이 증가에 영향 큼
Divide & Conquer	O(N log K)	균형 있는 병합 → 큰 입력 처리에 훨씬 빠름
PriorityQueue (Heap)	O(N log K)	우선순위 큐로 작은 값부터 추출