#2075. N번째 큰 수

방법 1. 메모리 초과

n x n개의 수를 우선순위 큐에 모두 추가한다. 이후 우선순위 큐에서 가장 큰 수를 n-1번 제거한 후, 가장 큰 수를 출력하면 n번째로 큰 수가 출력된다.

c++

int main() {
    
    priority_queue<int> pq;
    
    int n;
    cin >> n;
    
    // 우선순위 큐에 입력 받은 n x n개의 수를 모두 추가한다
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            int num;
            cin >> num;
            pq.push(num);
        }
    }
    
    // 우선순위 큐에서 가장 큰 수를 n-1번 제거한다
    for (int i=1; i<n; i++) {
        pq.pop();
    }
    
    // n번째로 큰 수가 출력된다
    cout << pq.top();
}

방법2.

위와 같이 우선순위 큐에 값을 추가해주지만, 큐의 길이가 n을 넘어가면 가장 작은 값을 제거해주면서 우선순위 큐의 길이를 n으로 유지해준다. 그럼 size가 n인 큐의 가장 작은 수가 n번째로 큰 수가 된다.

c++

int main() {

    priority_queue<int> pq;
    
    int n;
    cin >> n;
    
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            
            int num;
            cin >> num;
            
            // 우선순위 큐의 길이가 n개 이면
            if (pq.size() > n-1) {
            	// -num을 추가한 후, 가장 큰 값을 제거한다
                // -를 붙였기 때문에, 결국 가장 큰 값 = 가장 작은 값
                pq.push(-num);
                pq.pop();
            } else {
                pq.push(-num);
            }
        }
    }

    // -가장 큰 수 = 가장 작은 수 = n번째로 큰 수
    cout << -pq.top();
}