최소 힙

set<>을 활용해서 3명만 명예의 전당에 있고, 매일 명예의 전당에 오른 사람들 중 최하위 점수를 answer 벡터에 담아서 반환하는 문제를 풀었다.
하지만 시간 복잡도를 따졌을 때, 최소 힙을 사용하는 것이 더 효율적이라는 사실을 알았다.

[더 나은 풀이]

#include <string>
#include <vector>
#include <queue>

using namespace std;

vector<int> solution(int k, vector<int> score) {
    vector<int> answer;
    priority_queue<int, vector<int>, greater<int>> high; // 최소 힙 (오름차순)

    for(int i = 0; i < score.size(); i++) {
        high.push(score[i]); // 점수를 힙에 넣음
        
        // 상위 k명의 점수만 유지 (k명 이상일 때 가장 낮은 점수 삭제)
        if (high.size() > k) {
            high.pop(); // 가장 작은 원소 삭제 (맨 앞이 삭제되므로)
        }
        
        answer.push_back(high.top()); // 상위 k명의 점수 중 최저점수 추가
    }

    return answer;
}

priority_queue<int, vector<int>, greater<int>> high; 이 부분에서 최소 힙을 사용하여 점수를 자동으로 오름차순으로 정렬한다.
(가장 작은 값이 항상 top()에 위치하게 된다.

[원래 내 풀이]

#include <string>
#include <vector>
#include <set>

using namespace std;

vector<int> solution(int k, vector<int> score) {
    vector<int> answer;
    multiset<int> high; // 중복된 점수를 허용하기 위해 multiset 사용
    
    for (int i = 0; i < score.size(); i++) {
        high.insert(score[i]); // 새로운 점수를 삽입
        
        // 상위 k명의 점수만 유지 (multiset은 자동 정렬되므로 가장 작은 값을 관리)
        if (high.size() > k) {
            high.erase(high.begin()); // 가장 작은 원소 제거
        }
        
        // multiset에서 가장 작은 값은 항상 begin()에 있음
        answer.push_back(*high.begin());
    }

    return answer;
}