문제 풀이
단순하게 완전탐색법으로 접근하면 1초 안에 해결 가능한 범위이지만,
문제에서 보면 메모리 제한이 12MB로 다른 문제들에 비해서 무척이나 작은 공간이다.
12MB => 12 x 1000 x 1000
만약에 2차원 배열을 사용한다고 하면?
int(4byte) x 1500 x 1500 => 9,000,000 충분하다고 생각하지만 여기에 헤더 파일 등등 포함되면 빡빡하게 된다.
따라서 모든 자료를 저장할 필요 없이 N번째 큰 수를 찾아야 한다.
즉, 일부를 알기 위해서 전부를 저장할 필요가 없다.
우선순위 큐를 이용하는 방법이다.
다만 이때 우선순위 큐도 전체 자료를 저장하게 된다면, 마찬가지로 메모리 초과가 발생하게 된다. 이유는 위와 같다.
따라서 우선순위 큐를 사용하지만 일정 범위 이상으로 넘쳐흐르게 된다면 그중에서 필요 없는 값을 빼고 새로 들어온 값을 넣으면서 일부만 저장하는 방법을 취한다.
N = 3 이라고 할 때
입력값 : 3 5 6 7 8 이라고 하면,
처음 3 5 6 은 우선순위 큐에 저장하게 된다.
다음으로 들어온 숫자 7은 우선순위 큐(최소 힙)의 루트는 3이므로 3을 버리고 7을 넣는다.
왜? 3이라는 숫자는 필요 없는 값이기 때문에, 그렇지만 7이라는 숫자는 의미 있는 숫자이기 때문이다.
숫자 8이 들어오면 우선순위 큐의 루트는 5이므로 5를 버리고 8을 넣는다.
최종적으로는 우선순위 큐에는 6 7 8 이 존재하게 된다.
여기서 우리가 구하고자 하는 N = 3번째로 큰 수는 우선순위 큐의 루트인 6이 정답이 된다.
소스 코드
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int n, x;
priority_queue<int, vector<int>, greater<int> > pq;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> x;
pq.push(x);
if (pq.size() > n)
pq.pop();
}
}
cout << pq.top() << endl;
return 0;
}
'Algorithm' 카테고리의 다른 글
| [백준 14235] 크리스마스 선물 (0) | 2021.10.13 |
|---|---|
| [백준 1417] 국회위원 선거 (0) | 2021.10.13 |
| [백준 16926] 배열 돌리기1 (0) | 2021.10.12 |
| [백준 17298] 오큰수 (0) | 2021.10.11 |
| [백준 14425] 문자열 집합 (0) | 2021.10.11 |