백준 2075번 [N번째 큰 수](C++) -yes6686- 티스토리

백준 문제 풀이: 2075 [N번째 큰 수]

---

문제 링크: https://www.acmicpc.net/problem/2075

문제 설명:

N×N 크기의 행렬이 주어졌을 때, 이 행렬에서 N번째로 큰 수를 찾는 문제입니다.

가장 큰 값을 우선적으로 관리하는 우선순위 큐를 활용하여 해결할 수 있습니다.

---

문제 해결 코드

#include <iostream>
#include <queue>
using namespace std;

int arr[1501][1501]; // 행렬 저장 배열
priority_queue<pair<int, pair<int, int>>> pq; // 최대 힙

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n; // 행렬 크기 입력

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j]; // 행렬 원소 입력
            if (i == n - 1) pq.push({ arr[i][j], {i, j} }); // 마지막 행의 원소를 큐에 삽입
        }
    }

    int cnt = 0;
    while (!pq.empty()) {
        int k = pq.top().first;
        int i = pq.top().second.first;
        int j = pq.top().second.second;
        pq.pop();
        cnt++;

        if (cnt == n) { // N번째로 큰 수를 찾으면 출력 후 종료
            cout << k << '\n';
            break;
        } else {
            if (i != 0) { // 위쪽 행에서 새로운 원소 추가
                pq.push({ arr[i - 1][j], {i - 1, j} });
            }
        }
    }
}

예제 입력:

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번째 큰 값이 꺼내질 때 출력
• 시간 복잡도: O(N log N), 우선순위 큐를 이용한 연산

---

결과

주어진 행렬에서 N번째로 큰 수를 빠르게 찾아 출력할 수 있습니다. 우선순위 큐를 활용한 최적화된 탐색을 연습하기 좋은 문제입니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!