C++ / 프로그래머스 / 명예의 전당 (1)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/138477

프로그래머스

문제풀이

오름차순으로 정렬하는 우선순위 큐를 이용해 풀었다.

우선순위 큐의 top에는 가장 작은 점수가 있으므로, 우선순위 큐에 k개 미만의 점수만 있을 경우 우선순위 큐와 answer에 push 한다.

우선순위 큐의 사이즈가 k개 일 때부터는 우선순위의 top과 새로 들어오는 점수를 비교해서 더 높은 점수를 우선순위 큐에 넣는다.

 

코드

#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>>rating;
    int idx(0);
    for (idx = 0; idx < score.size(); ++idx) {
        if (rating.size() < k) {
            rating.push(score[idx]);
        }
        else if (rating.top() < score[idx]) {
            rating.push(score[idx]);
            rating.pop();
        }
        answer.push_back(rating.top());

    }
    return answer;
}