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

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

2075번: N번째 큰 수

문제 풀이의 조건을 자세히 잘 보면 풀기 쉬운 문제이다.

우선 모든 input을 받아놓을 수는 없다. 메모리가 최대 12MB이기 때문에 입력받자마자 바로바로 처리를 해야 한다.

대신 큰 N개의 수만 저장하여 관리하여야 하는데, 이 때 N개 중에서 가장 작은 수를 최대한 빠르게 알아낼 수 있어야 한다.

 

처음에는 vector에 삽입하고 정렬하기를 반복하려 했다.

하지만 이 경우 최악의 경우 시간복잡도가 O(N)이다. 상당히 비효율적일 수 있다.

 

그래서 vector보다는 균형 이진 트리 기반으로 구현된 set을 쓰면 삽입 후에 따로 정렬을 해줄 필요가 없다.

삽입과 동시에 정렬이 이루어지기 때문이다.

 

#include <iostream>
#include <set>
#include <vector>
using namespace std;
set<int> s;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, num;
    cin >> n;

    for(int i = 0;i < n;i++) {
        for(int j = 0;j < n;j++) {
            cin >> num;
            if(s.size() < n) {
                s.insert(num);
            }
            else if(s.size() == n){
                int min_num = *s.begin();
                if(min_num < num) {
                    s.erase(min_num);
                    s.insert(num);
                }
            }
        }
    }
    
    cout << *s.begin() << '\n';
}