백준 2075번 N번째 큰 수 C++

백준 N번째 큰 수 2075 C++

문제 설명

문제

N×N의 표에 수 N²개가 채워져 있습니다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것입니다. N=5일 때의 예시는 다음과 같습니다.

12 7 9 15 5
13 8 11 19 6
21 10 26 31 16
48 14 28 35 25
52 20 32 41 49

이러한 표가 주어졌을 때, N번째 큰 수를 찾아야 합니다. 표에 적힌 수는 모두 다릅니다.

---

테스트케이스

입력:

5
12 7 9 15 5
13 8 11 19 6
21 10 26 31 16
48 14 28 35 25
52 20 32 41 49

출력:

35

---

작동원리

N×N의 모든 수 중 N번째로 큰 값을 찾기 위해, 모든 값을 다 정렬하는 방법도 있지만, 메모리와 시간을 절약하기 위해 최소 힙(min-heap)을 활용합니다.

• 최소 힙은 항상 가장 작은 값이 맨 위에 오도록 유지됩니다.
• 모든 값을 읽으면서 힙에 삽입하되, 힙의 크기를 N으로 제한합니다.
• 크기가 N을 초과하면, 힙의 맨 위(가장 작은 값)를 제거합니다.
• 이렇게 하면 힙 안에는 항상 지금까지 읽은 값 중 가장 큰 N개가 남게 됩니다.
• 마지막에 힙의 top()을 출력하면, 그 값이 전체 중 N번째 큰 값입니다.
• 즉, 정렬 없이도 N번째 큰 값을 구할 수 있습니다.

---

아이디어

• 모든 원소를 최소 힙에 하나씩 넣습니다.
• 힙의 크기를 항상 N으로 유지합니다.
• 힙에 원소를 넣을 때마다 크기가 N을 초과하면 pop()을 실행하여 가장 작은 원소를 제거합니다.
• 이렇게 하면 힙 내부에는 항상 상위 N개의 값만 남습니다.

예를 들어, N=3이고 입력이 [5, 1, 9, 3, 10, 7, 6, 2, 8]이라면:

• 처음 3개(5, 1, 9)를 넣으면 힙 = [1, 5, 9] (1이 top)
• 다음 값 3 → 크기 초과 시 1 제거, 힙 = [3, 5, 9]
• 다음 값 10 → 3 제거, 힙 = [5, 9, 10]
• 다음 값 7 → 5 제거, 힙 = [7, 10, 9]
• 다음 값 6 → 6은 top(7)보다 작으므로 무시하는 대신, 코드에서는 일단 넣고 pop
• 마지막 값 8 → top(7) 제거, 힙 = [8, 10, 9]

최종 힙의 top은 8, 즉 전체 중 3번째 큰 값입니다.

이런 방식은 모든 값을 정렬하는 O(N² log N²)보다 훨씬 빠른 O(N² log N) 시간에 N번째 큰 값을 찾을 수 있습니다.

---

전체코드

#include <iostream>
#include <queue>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    priority_queue<int, vector<int>, greater<int>> pq; // 최소 힙
    int x;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> x;
            pq.push(x); // 값 삽입
            if (pq.size() > N) // 크기 초과 시 최소값 제거
                pq.pop();
        }
    }
    cout << pq.top() << "\n"; // N번째 큰 값 출력
}

---

결론

이 문제는 N²개의 수 중 N번째 큰 값을 구하는 문제로, 모든 수를 정렬하는 대신 크기 N의 최소 힙을 사용하면 효율적으로 해결할 수 있습니다.

힙의 크기를 N으로 유지하면서 입력을 처리하면, 힙 안에는 항상 가장 큰 N개의 수가 남게 되고, 그 중 최소값이 전체에서 N번째 큰 값이 됩니다.

이 방식은 시간 복잡도가 O(N² log N)으로, 제한 시간 내에 충분히 동작하며 메모리 사용도 최소화됩니다.

---