[Algorithm]Baekjoon 2075번 :: N번째 큰 수

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

2075번: N번째 큰 수

 
int n, input;
priority_queue<int, vector<int>, greater<int>> pq;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    for (int i = 0; i < n*n; ++i)
    {
        cin >> input;
 
        if (pq.size() < n)
        {
            pq.push(input);
        }
        else if(pq.size() == n)
        {
            if (input > pq.top())
            {
                pq.pop();
                pq.push(input);
            }
        }
    }
 
    cout << pq.top();
}

 

 

문제 설명만 읽으면 '걍 값 다 벡터에 넣고 정렬돌리면 되는거 아닌가?' 하지만, 메모리제한이 포인트다.

N값은 최대 1500이고 인풋개수는 최대 1500 * 1500이다. int형으로 받아야하니 input 메모리만 거의 9메가바이트? 정도 되고, 헤더 include 하면 또 메모리가 추가되서 무조건 메모리초과가 뜬다.

 

애초에 이 문제는 당연히 저렇게 쉽게 푸는게 아니라는 문제이다.

최소한의 메모리 사용을 하면서 풀어야하는 문제이다.

결국 n번째 큰값을 알아야하는 문제이니, 우선순위큐에다가 큰값들 n개를 계속 유지시키는 방향으로 코드를 작성했다.

그렇게 하려면 일단 우선순위큐를 greater<int>, 즉 가장 작은값이 top에 오도록 설정해놓고 값을 넣으면 된다.

그리고 n개만큼 값을 집어넣은 후, 그다음에 들어오는 값이 우선순위큐의 top()보다 크면은 우선순위큐를 pop한다음 인풋값을 push하면 된다. 즉, 우선순위큐에서 제일 작은값들을 뺴면서 우선순위큐를 점점 큰값들로만 채우는거다.

결국 끝까지 로직을 수행하다보면 우선순위큐에는 제일 큰값들부터 담겨있게 되기 때문에, 마지막에 그냥 우선순위큐의 top을 출력하면 끝이다.