백준 2075번 C++ 풀이

https://www.acmicpc.net/problem/2075

2075번: N번째 큰 수

시간 제한	메모리 제한	solved.ac 티어
1초	12MB(하단 참고)	실버 2

문제

N×N의 표에 수 N^2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. 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번째 큰 수를 출력한다.

---

처음에는 1500 * 1500 * 4Byte = 9백만Byte이고, 이를 MB단위로 변환하면 9MB정도 나오기 때문에 메모리제한에 걸리지 않을 것 같아서, 그냥 단순하게 모든 숫자를 우선순위 큐에 저장했다. 하지만, 메모리 초과가 발생하였다. 보통 C++17로 제출하면, 2020KB정도 깔고 들어가던데, 이거랑 우선순위 큐에서 내부적으로 사용하는 변수들의 용량까지 합쳐서 메모리가 초과된거 같다. 왜 2020KB를 사용하는지는 식견이 짧아 잘 모르겠다.

 

어쨌든 우리는 전체 숫자를 저장하는건 답이 아니라는 것은 알았다. 그렇다면 전체를 저장해야하는 문제가 아니라는 뜻이다. 생각을 해보면, 어짜피 N번째 숫자만 알면 되니까, N개만 저장하고, 저장한 곳에는 가장 큰 숫자들부터 시작해서 N개만 담아둔다면, 맨 마지막에는 최댓값 ~ N번째 숫자만이 들어있을 것이다. 정렬로도 해볼까 하다가, std::sort는 O(nlogn)의 시간복잡도를 가지고, 이를 n*n번 해야하기 때문에, 시간초과가 당연히 날 것이고, 그렇기에 우선순위 큐를 사용했다.

 

#include <bits/stdc++.h>
using namespace std;

void sol(int n) {
    priority_queue<int, vector<int>, greater<int>> pq;
    int temp;
    for(int i = 0; i < n * n; i++) {
        cin >> temp;
        pq.push(temp);
        if(pq.size() > n) pq.pop();
    }
    cout << pq.top();
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    sol(n);
}