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

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 우선순위큐를 활용해 풀었다. N개의 수를 저장하는 우선순위 큐를 오름차순으로 정렬하여 가장 작은 수를 먼저 삭제해주는 방식으로 풀었다.

처음에는 단순하게 N x N의 모든 수를 우선순위 큐에 저장하고, 앞의 N - 1개의 수를 삭제해주고 난 뒤 가장 앞에 남게 되는 수를 반환하면 N번째 큰 수를 구할 수 있을 것으로 생각했다. 하지만 해당 문제는 메모리 제한이 작게 되어있기 때문에 이 방식으로 풀 경우 메모리 초과가 발생했다.

때문에 우선순위 큐에 모든 수를 저장하지 않고 N개의 수만 저장하는 방식으로 풀었다.

1) 칸에 들어있는 수를 저장하는 우선순위 큐를 선언한다. 해당 우선순위 큐는 오름차순으로 정렬된다.
2) 첫 행에서 가장 큰 수를 구해 이를 int형 변수 min에 저장하고, 그 수를 우선순위 큐에 삽입한다.

• 해당 문제에서 자신의 아래 칸에 있는 수는 모두 자기보다 큰 수들이다. 따라서 첫 행의 가장 큰 수의 아래에 위치한 수들은 항상 해당 수보다 크기 때문에 가장 큰 N개의 수에 첫 행의 가장 큰 수보다 작은 수는 절대로 해당될 수 없으므로 해당 수를 가장 먼저 우선순위 큐에 넣는다.

3) 그 이후로 두번째 줄부터 N번째 줄까지 모든 수를 확인한다.

• (현재 확인하는 수 > 우선순위 큐의 가장 앞에 위치한 수)일 때
  : 우선순위 큐에 삽입 (push)
• (push 이후의 우선순위 큐 길이 > n)일 때
  : 우선순위 큐 맨 앞의 원소를 제거 (pop)
  

4) 위 과정을 반복하면 우선순위 큐에는 가장 큰 N개의 수들만 남아있게 되고, 이 중에 가장 앞에 위치한 수가 N번째로 큰 수이게 된다.

🖥️ 풀이 코드

#include <stdio.h>
#include <iostream>
#include <queue>

using namespace std;

int main(int argc, char** argv)
{
	ios::sync_with_stdio(false);
	cin.tie(); cout.tie();

	int n = 0;
	cin >> n;
	priority_queue<int, vector<int>, greater<int>> pq;	// 오름차순 정렬 우선순위 큐

	int min = -1000000000;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			int num;
			cin >> num;

			// 첫 행에서 가장 큰 수를 min으로 설정하고, 그 수를 우선순위 큐에 삽입
			if (i == 0)
			{
				if (num > min)
					min = num;	
				
				if (j == n - 1)
					pq.push(min);
			}
			else
			{
				// 오름차순 정렬 되어있기 때문에 top()이 가장 작다. 가장 작은 값보다 클 때만 push 한다. 
				if (num > pq.top())
					pq.push(num);

				// 길이가 n을 넘어가면 맨 앞의 가장 작은 수를 제거한다.
				if (pq.size() > n)
					pq.pop();
			}
		}
	}
	cout << pq.top();
}