2075_N번째 큰 수

Concept & Idea

처음에 문제 이해가 잘 안되서 좀 당황했다. 나는 N번째 큰수 라는 제목을 보고 왜 뒤에서 N번째로 큰수라고 해석했는지..

문제는 간단하다. 입력대로 받은 수 중에 N번째로 큰수를 찾으면 되는 문제!
이 문제에 키포인트는 메모리에 있다. 
N이 1500이면 우선순위큐에 데이터를 1500*1500개까지 받을 것이냐?
그렇지 않다. 

어차피 앞에서 몇번째로 큰지가 중요하기 때문에 뒤에서 뒤에 쓸모없는 작은 숫자들은 버려져도 된다.

처음엔 어떻게 해서 뒤에 녀석들을 다 빼지..?
포문을 돌려..? 라는 생각을 했으나 전체 수에 -를 곱해서 넣으면 해결 할 수 있다. 

12 -> 7 -> 9 -> 15 -> 5 순서로 들어와도
-5 -> -7 -> -9 -> -12 -> -15 순으로 입력될 것이기 때문에 사이즈가 넘어가면 pop()을 하면 전체 사이즈를 n 만큼 유지할 수 있다.

Top()에는 n개중 제일 작은 녀석이 앞에 있을테니 그대로 -1 * top을 출력해주면 된다. 

Code

#include <iostream>
#include <queue>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    priority_queue<int> pq;
    for(int i=0; i<n*n; i++) {
        int num;
        cin>>num;
        pq.push(-num);
        if(pq.size()>n) {
            pq.pop();
        }
    }
    cout<<-pq.top()<<"\n";
}

 

Fealing

불필요한 데이터를 제거하는 법을 잘 생각해내면 좋으련만.. 

많이 부족하다...