[C++][프로그래머스][Heap] 더 맵게

[문제]

코딩테스트 연습 - 더 맵게

스코빌 지수가 가장 낮은 두가지 음식을 섞어서 모든 음식이 K이상의 스코빌 지수를 가지게 하려 할 때 필요한 최소 연산 횟수를 구하는 것.

 

[풀이]

처음엔 걍 STL algorithm의 sort() 함수로 scoville 벡터를 내림차순 정렬하고 scoville 벡터의 가장 작은 값과 두번째로 작은 값을 K보다 커질 때까지 연산하는 과정을 반복했다. 결과는 효율성 테스트 0점.

#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> scoville, int K) { // scoville: 2 이상 1,000,000 이하
    int answer = 0;

    int first_low_scoville = 0;
    int second_low_scoville = 0;
    
    sort(scoville.begin(), scoville.end(), greater<int>()); //내림차순 정렬
    
    while(scoville.back() < K){
        if(scoville.size() < 2) return -1;

        first_low_scoville = scoville.back();
        scoville.pop_back();
        second_low_scoville = scoville.back();
        scoville.pop_back();
        
        scoville.push_back(first_low_scoville + (second_low_scoville*2));
        sort(scoville.begin(), scoville.end(), greater<int>()); //내림차순 정렬
        
        answer++;
    }
    return answer;
}

 

문제 유형에 맞게 Heap 자료구조(Priority queue)를 이용해서 시간을 단축시켜야 했다.

 

priority queue는 root에 가장 작은 값이 놓이는 완전 이진 트리 구조를 갖는다. 완전 이진 트리 구조이므로 삽입/삭제/탐색 시간복잡도를 O(logN)로 줄일 수 있다. 그래서 이 문제처럼 빠르게 최소값/최대값을 찾아야 할 때 유용하게 사용할 수 있다. 

 

[코드]

#include <vector>
#include <queue>
using namespace std;

int solution(vector<int> scoville, int K) { // scoville: 2 이상 1,000,000 이하
    int answer = 0;
    
    int first_low_scoville;
    int second_low_scoville;
    
    priority_queue<int, vector<int>, greater<int>> pq(scoville.begin(), scoville.end());
    
    while(pq.top() < K){
        if(pq.size() <=1 ) return -1;
        
        first_low_scoville = pq.top();
        pq.pop();
        second_low_scoville = pq.top();
        pq.pop();

        pq.push(first_low_scoville + second_low_scoville*2);
        answer++;
    }
    
    return answer;
}