더 맵게 (feat. 프로그래머스, 42626번)

더 맵게
https://programmers.co.kr/learn/courses/30/lessons/42626

프로그래머스

반응형

// woohyeon.kim
#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int, vector<int>, greater<int>> tmpl;
    for(const auto& v : scoville)
        tmpl.push(v);
    auto first_min_value = tmpl.top();
    while((tmpl.size() > 1) && (first_min_value < K))
    {
        tmpl.pop();
        auto second_min_value = tmpl.top();
        tmpl.pop();
        auto new_scoville = first_min_value + (second_min_value * 2);
        tmpl.push(new_scoville);
        ++answer;
        first_min_value = tmpl.top();
    }
    
    if((answer == 0) || (first_min_value < K))         answer = -1;
    return answer;
}
// *&)*@*

처음 vector를 사용해서 sort를 수행했는데, 효율성이 모두 fail이 나서

priority_queue로 변경하였습니다.

이미 대부분 정렬이 되어 있는 vector에 sort를 수행하는건 비효율적입니다.

priority_queue는 삽입 시점에 우선순위에 맞춰 삽입되니 참고하세요!