[백준] 2075번 - N번째 큰 수

www.acmicpc.net

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

문제

💡

N×N의 표에 수 N^2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자. 아래와 같은 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.

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초

메모리 제한: 12MB

입력

💡

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

출력

💡

첫째 줄에 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이 1500일 때, int 자료형이므로 1500*1500*4 = 9,000,000 = 9MB이다. 메모리 제한인 12MB를 초과하지 않아 N크기의 우선순위 큐를 만들었다.

그런데 메모리 초과가 나왔다.


	priority_queue<int> pq;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			int input;
			cin >> input;
			pq.push(input);
		}
	}

	for (int i = 0; i < n - 1; ++i) {
		pq.pop();
	}

	cout << pq.top();

생각해 보니, 우선순위 큐는 정렬 과정에서 추가 메모리가 사용되서 그런 것 같다.

N번째 수만 찾으면 되니 입력시 크기가 N을 넘어서지 않게 조정하고, N번째 수를 쉽게 찾기 위해 최소힙을 사용했다. 이후 시간초과가 발생해서 입출력 최적화를 통해 해결하였다.

코드


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

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

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

	cout << pq.top();
	return 0;