Kth Smallest Element in a Sorted Matrix

Solve 1) K-way Merge (Heap)

Solve 2) Binary Search

문제 요약

• n × n 행렬 matrix

  • 각 행·열이 모두 오름차순으로 정렬

• 정렬 전체 순서에서 k번째 원소를 찾아라.

• 제약: 1 ≤ n ≤ 300, 1 ≤ k ≤ n², |matrix[i][j]| ≤ 10⁹

• 메모리는 O(n²) 보다 작아야 한다.

---

직관 ▶ 두 가지로 압축하기

방법	아이디어	메모리	언제 좋을까
① 다중 병합 힙	각 열(행)의 첫 원소만 미니 힙에 넣고, 팝할 때마다 같은 열(행)의 다음 행(열)을 푸시	O(n)	k 가 작을 때 빠름
② 값 이분 탐색	값 범위를 [최소, 최대] 로 두고, 중간값 ≤ X 인 원소 개수를 세어 범위 수축	O(1)	k 가 크거나 메모리 제약 클 때

아래에서는 힙 방법을 중심으로 서술한다.

---

1️⃣ 핵심 식 – 힙 불변식

힙에는 “각 열(행)에서 아직 꺼내지 않은 최솟값”만 남는다.

• 꺼낸 노드 (r, c) 뒤에는 동일 행의 c+1 열 값만 새로 추가한다.
• 따라서 힙 크기는 항상 ≤ n.

---

2️⃣ 불변식(Invariant)

• 반복 i 단계 직후:

  • 이미 i 개의 최소값이 확정되었고,
  • 힙에는 아직 고려되지 않은 후보 중 최소값들이 들어 있다.

• 이 불변식이 유지되므로, k 번째 팝된 노드가 곧 답.

---

3️⃣ 알고리즘 (K-way Merge)

변수	의미
pq	min-heap<Node>
Node {val,r,c}	값·행·열 인덱스

int kthSmallest(vector<vector<int>>& a, int k){
    struct Node{
        int val,r,c;
        bool operator>(const Node& o) const { return val > o.val; }
    };
    int n = a.size();
    priority_queue<Node, vector<Node>, greater<Node>> pq;

    // ① 각 행의 0-열 삽입
    for(int r=0;r<n;++r)
        pq.push({a[r][0], r, 0});

    // ② k-1 번 팝 & 다음 열 푸시
    for(int i=0;i<k-1;++i){
        auto [v,r,c] = pq.top(); pq.pop();
        if(c+1 < n) pq.push({a[r][c+1], r, c+1});
    }
    return pq.top().val;   // k번째
}

---

4️⃣ 복잡도 분석

	시간	메모리	비고
힙	O(k log n)	O(n)	힙 크기 ≤ n
이분 탐색	O(n log (range))	O(1)	range ≈ max−min

---

5️⃣ 시각적 흐름 (예: n=3, k=5)

행렬:
1  5  9
2  6 10
3  7 11

힙에 들어가는 데이터 (val, r, c)
초기 힙: (1,0,0) (2,1,0) (3,2,0)
팝1 → 1   푸시 (5,0,1)
팝2 → 2   푸시 (6,1,1)
팝3 → 3   푸시 (7,2,1)
팝4 → 5   푸시 (9,0,2)
팝5 → 6   ← k번째 답!

(행,열 움직임이 한눈에 보인다.)

---

6️⃣ 왜 O(n) 메모리가 충분한가? – 귀류법 스케치

1. 힙에 어떤 행에서 두 개 이상의 원소가 동시에 존재한다고 가정.

2. 더 앞선 열 값이 반드시 뒤 열 값보다 작으므로,

   • 앞선 열 값이 더 빨리 팝된다.
   • 그러면 뒤 열 값은 같은 행의 “최솟값” 조건을 잠시라도 충족할 수 없다.

3. 모순 → 각 행은 힙에 최대 1 개만 남는다.

---

마무리 & 확장 학습

• 같은 패턴 문제

  • LeetCode 373. Find K Pairs with Smallest Sums – 두 배열 다중 병합
  • LeetCode 264. Ugly Number II – 중복 제거 다중 포인터

• 값 이분 탐색 연습

  • LeetCode 668. Kth Smallest Number in Multiplication Table