N번째 큰 수

알고리즘 구분 : 우선순위 큐, 자료 구조

문제

N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. 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번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.

입력
첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.

출력
첫째 줄에 N번째 큰 수를 출력한다.

예제 입력 1
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
예제 출력 1
35

문제 풀이

단순하게 주어진 NN개의 수 중 N번째로 큰 수를 출력하면 되는 문제이다.
문제의 주요 특징은 메모리 제한이 12MB로 굉장히 작은 편이며, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다.
일단 메모리 제한이 굉장히 작기 때문에, 배열을 순환하면서 탐색하는 과정은 총 주어지는 수가 NN 최대 1500 * 1500이기에 MLE가 날 것이다. 그렇기에 우선순위 큐를 활용하여 N번째로 큰 수의 위치만 계속 바꿔주는 과정으로 문제를 풀어야 한다.
N번째로 큰 수가 계속 우선순위 큐의 top에 위치하여야 하기 때문에, 우선순위 큐는 오름차순(greater)로 정렬이 되어야 한다.
첫 번째 줄은 별다른 조건 확인 없이 입력을 받지만, 두 번째 줄부터는 무조건 자신의 한 칸 위의 수보다는 크기가 크기에, 우선순위 큐 내에서 N번째 자리의 수의 값이 바뀔 수 밖에 없다. 그렇기에, 조건문을 통해 현재 우선순위 큐에서 N번째 자리에 위치한 값과 현재의 입력값을 비교하고, 현재의 입력값이 더 크다면, N번째 자리에 위치한 값을 pop하고 현재의 입력값을 push하는 과정을 거치도록 구현하면 된다.

소스 코드

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

int n;
priority_queue<int, vector<int>, greater<int>> pq; //내림차순 정렬

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

    cin >> n;
    for(int i = 0; i < n * n; i++) {
        int input;
        cin >> input;
        if(i < n) {
            pq.push(input);
        }
        else {
            if(pq.top() < input) {
                pq.pop();
                pq.push(input);
            }
            else {
                continue;
            }
        }
    }

    cout << pq.top() << endl;

    return 0;
}

• 문제 출처 : https://www.acmicpc.net/problem/2075
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.