C++ 백준 2075 N번째 큰 수

백준 2075

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

2075번: N번째 큰 수

풀이 전 나의 생각

N x N의 표가 주어질 때, 모든 수는 자신의 한 칸 위에 있는 수보다 크다.
이때, N번째로 큰 수를 찾아야 한다.

 

조건

- N(1 ≤ N ≤ 1,500)

- 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수

 

과정

이 문제는 메모리 제한이 12MB기 때문에 N의 정보를
모두 넣어서 풀려고하면 메모리 초과가 발생한다.

 

이를 인지하고 설명을 보면 모든 수는 자신의 한 칸위에 있는 수보다 크다고 한다.

그러면 한 칸씩 정보를 받으면서 N번째로 큰 수를 계속 갱신해주면
메모리 제한도 지킬 수 있고 원하는 답도 구할 수 있다.

 

따라서 우선순위 큐를 내림차순 비교식으로 선언하고
N번째 크기에 맞춰 작은 값들을 계속 pop을 해나간다면
결국 top에 있는 수는 N번째로 큰 수가 된다.

예를 들어, N = 5, 큐 = {12, 7, 9, 15, 5}, 다음 칸 정보 = {13, 8, 11, 19, 6}가 있다고 가정할 때
현재 큐에 다음 칸 정보가 들어오고 ({5, 6, 7, 8, 9, 11, 12, 13, 15, 19})
N의 크기만큼 pop을 해준다면 {11, 12, 13, 15 ,19}가 남아서
N의 수인 5번째로 큰 수가 11이 된다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>
#include <deque>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int N;
	cin >> N;

	//내림차순 비교
	priority_queue<int, vector<int>, greater<int>> pq;
	
	for (int i = 0; i < N; i++)
	{
		// 한 칸마다 정보를 큐에 삽입, 메모리 초과를 방지하기 위해
		for (int j = 0; j < N; j++)
		{
			int val;
			cin >> val;
			pq.push(val);
		}

		// N번째 큰 수를 찾기 위해 N의 크기만큼 top 값 제거
		while (pq.size() > N)
		{
			pq.pop();
		}
	}

	cout << pq.top();
}