[c++] 백준 2075 : N번째 큰 수

[c++] 백준 2075 : N번째 큰 수

🥈실버 2

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

2075번: N번째 큰 수

---

접근

메모리 제한이 있는 문제라 최대한 적은 공간을 활용해야 한다.

 

처음엔 그냥 N^2개의 값을 입력받고 우선순위 큐에 다 때려넣으면 최대힙으로 내림차순 정렬될 것이기 때문이므로 N-1만큼 pop하여 N번째 값을 가져오려는 시도를 했는데 시간초과가 나거나 메모리 초과 에러가 발생했다.

 

대안으로, 우선순위 큐를 사용하되 N^2개가 아니라 N개만 사용하는 방식으로 문제를 해결할 수 있었다.

예제의 첫번째 줄을 최소힙으로 받으면 위와 같은 그림이 될 것이다.

예제의 경우에는 25개의 입력값 중 5번째로 큰 값을 출력하라고 한다.

 

만약 최소힙으로 우선순위 큐의 공간을 5개로 제한하면 top의 값은 그 다섯 개의 값중 가장 작은 값이 오게 된다. 이때 우선 순위 큐 내부의 값은 top의 값 이상의 수로 이루어져 있다.

 

모든 입력값에 대해서 현재 top보다 큰 값의 경우에는 현재 top을 pop으로 빼버리고 새로운 값을 push를 하게되면 공간을 5개만 사용하되, push와 pop의 빈도까지 줄일 수 있다. top의 값이 점차 증가하기 때문에 top보다 작은 값에 대해서는 무시할 수 있기 때문이다.

 

최초의 N개에 대해서는 우선순위 큐에 push하되, 나머지 N^2 - N개에 대해서 이 연산을 반복해서 진행하면 최종적으로 top의 값은 전체 입력 값들 중 N번째로 큰 수가 된다.

 

코드

#include <iostream>
#include <queue>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    priority_queue<int, vector<int>, greater<int>> pq; // 최소힙으로 선언

    for (int i = 0; i < N; i++) {
        int num;
        cin >> num;
        pq.push(num);
    }

    for (int i = N; i < N*N; i++) {
        int num;
        cin >> num;
        if (num > pq.top()) {
            pq.pop();
            pq.push(num);
        }
    }
    cout << pq.top();
}

ios::sync_with_stdio(false)

cin.tie(0)

위의 두 구문은 c와 c++ 표준 스트림 사이의 동기화를 비활성화하고 입력 스트림의 테더링을 해제하여 입/출력 속도를 향상시키기 때문에 사용하지 않는 경우 시간 초과가 발생할 수 있다.