[ BOJ 2075 ] N번째 큰 수

http://icpc.me/2075

문제

N*N의 격자판에 숫자가 들어온다.

이 격자판에 있는 숫자 중 N번째로 큰 수를 출력하라.

풀이

이 문제는 메모리가 12MB밖에 안된다.

왜 이렇게 작게 해놨느냐? 2차원배열을 만들거나 그냥 vector int해서 하면 MLE가 뜬다.

계산했을땐 8MB였는데 왜 MLE 뜨는지 모르겠다. 에반데

따라서 다른 전략을 써야한다.

이 문제에서 가장 중요한 것은 N번째로 큰 수를 출력한다는 것에 있다.

즉 우리가 실제로 필요한 수의 개수는 "이 때까지 받았던 수들 중 N번째로 큰 수들의 모임"이 필요하다.

만약 다음에 받는 수가 저기에 들어가면 바꿔주면 되기 때문이다.

예를 들어보자.

8번째로 큰 수를 출력하는 상황이고, 배열에 2, 4, 5, 6, 7, 8, 9, 10 가 있다.

이 때 1이 들어왔다 하자.,

그러면 1은 9번째로 큰 수이므로 딱히 필요한 수가 아니다. 따라서 1을 배열에 넣지도 않는 것이다. 왜냐면 딱히 유용한 정보가 아니기 때문이다.

다음으로 3이 들어왔다 하자.

3은 8번째로 큰 수이므로 필요한 수다. 추가적으로 2는 9번째로 큰 수로 밀리게 된다. 즉, 2가 필요가 없어지고 3이 필요가 있어진다.

따라서 배열에서 2를 3으로 바꾼다.

이를 구현하기 위해서 배열을 쓰는 것은 굉장히 불편하다.

왜냐면 결론적으로 배열에서 가장 작은 수와 들어오는 수를 비교해서 바꿔주는 것인데, 바꿔주고 나서 다시 정렬이 필요하기 때문이다.

즉, 항상 정렬이 유지되어 있는 자료구조가 있으면 편하다.

이러한 자료구조로는 priority_queue가 있다,

Min heap을 만들어서 가장 작은수와 비교후 바꿔야 하면 그 원소를 넣고 작은수를 pop한다.

코드는 다음과 같다.

코드

#include <bits/stdc++.h>
using namespace std;
int main()
{
    priority_queue<int,vector<int>, greater<int> > pq;
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++) for(int j=0,num;j<n;j++)
    {
        scanf("%d",&num);
        if(pq.size()<n) pq.push(num);
        else
        {
            pq.push(num), pq.pop();
        }
    }
    return !printf("%d",pq.top());
}