[백준/Baekjoon] 2075 N번째 큰 수 C++ :: Data structure & Priority queue

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

2075번: N번째 큰 수

---

1. Logic

- 메모리 제한이 12MB밖에 안되기 때문에 자료구조에 들어가는 데이터의 갯수를 최대한 적게 넣어야한다. 

우선순위 큐를 활용해 -를 붙혀서 오름차순으로 정리해 주고 갯수는 N개 만큼 가지고 있는다.

우선순위 큐의 가장 앞에 있는 수는 -를 떼고 나면 가장 작은 숫자이기 때문에 N개만큼 유지하면서 가장 작은 숫자인 -pq.top보다 큰 숫자가 오면 pq.top을 pop하고 새로운 숫자를 push해서 지속적으로 N개만큼 유지한 후 입력을 다 받은 뒤 pq.top의 값을 확인하면 된다.

---

2. Code

#include<bits/stdc++.h>

using namespace std;

priority_queue<int> pq;
priority_queue<int> temp;

int n;

int main() {
    ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0);
    
    cin >> n;
    
    for(int i = 0; i < n * n; i++) {
        int a;
        cin >> a;
        
        if(pq.size() < n) {
            pq.push(-a);
        }
        else {
            if(-pq.top() < a) {
                pq.push(-a);
                pq.pop();
            }
        }
    }
    
    cout << -pq.top();
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90