문제

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

풀이

1차원 배열에 저장하기

// 벡터 사용하면, 메모리 초과 
#include <iostream> 
#include <vector> 
#include <string>
#include <algorithm> 
using namespace std;

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

	int n;
	cin >> n; // 최대 1500 

	vector<int> arr;
	for(int i = 0; i < n * n; i++){ // 최대 225만 * 4B = 9MB
		int e; 
		cin >> e; 
		arr.push_back(e); 
	}

	sort(arr.begin(), arr.end(), greater<int>()); 
	cout << arr[n - 1] << endl;
	
	return 0;
}

// 일반 배열 사용하면, 메모리 초과 X 
#include <iostream> 
#include <vector> 
#include <string>
#include <algorithm> 
using namespace std;

const int MAX = 1500;
int arr[MAX * MAX + 1];

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

	int n;
	cin >> n; // 최대 1500 
	
	for(int i = 0; i < n * n; i++){ // 최대 225만 * 4B = 9MB
		cin >> arr[i]; 
	}

	sort(arr, arr + n * n, greater<int>()); 
	cout << arr[n - 1] << endl;
	
	return 0;
}

메모리 초과를 방지하려면

계수 정렬을 적용할 수 있는지 봤더니, 입력값으로 음수가 가능하고 최대 크기도 10억이나 된다. 따라서 계수 정렬도 적합하지 않다.

다른 블로그들을 참고하여 메모리를 절약할 수 있는 방법을 알아냈다. 바로 우선순위 큐에 모든 원소를 다 저장하는 게 아니라, N개의 원소만 저장하는 것이다.

최소 힙으로 구현된 우선순위 큐의 사이즈가 N을 넘을 때마다 최솟값부터 pop 되도록 구현하면, 마지막에는 크기가 가장 큰 원소 N개가 남게 된다. 그 N개 중에서 가장 작은 top을 출력하면 그게 곧 N번째로 큰 수가 된다.

#include <iostream> 
#include <vector> 
#include <string>
#include <algorithm> 
#include <queue> 
using namespace std;

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

	int n;
	cin >> n; // 최대 1500 

	priority_queue<int, vector<int>, greater<int>> pq; // 최소 힙 
	
	for(int i = 0; i < n * n; i++){
		int e; 
		cin >> e; 
		pq.push(e); 
		if(pq.size() > n) pq.pop(); // 작은 수부터 pop 되도록 
	} 

	// 남아있는 원소: 35 41 48 49 52 
	// while(!pq.empty()){
	// 	cout << pq.top() << " ";
	// 	pq.pop(); 
	// }

	// N번째로 큰 수 출력 
	cout << pq.top() << endl; 
	
	return 0;
}

메모리 사용량이 확연히 줄어든 것을 볼 수 있다!!