[프로그래머스] 더 맵게 문제 풀이

https://programmers.co.kr/learn/courses/30/lessons/42626#

코딩테스트 연습 - 더 맵게

 

최소값 2개를 꺼내서 연산을 반복해서 K 이상 만들 수 있는지 푸는 문제이다.

 

매번 최소값이 필요하기 때문에

최소값을 빠르게 구하는 방법이 중요하다.

min heap을 사용하면 금방 풀 수 있다.

 

c++ STL에서 priority_queue 를 사용하면 금방 풀 수 있지만,

직접 구현하는 것이 의미가 있다.

 

priority_queue를 이용해서 간단히 푸는 방법은

priority_queue는 기본적으로 max heap으로 설정되어 있다.

그래서 min heap으로 바꿔줘야하는데 

priority_queue<int, vector<int>, greater<int>> 로 정의하면 된다.

 

직접 구현하는 하는 코드는 아래와 같다.

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void push(vector<int>& pq, int val) {
    pq.push_back(val);
    
    int i = pq.size()-1;
    int p = (i-1)/2;
    while(i > 0 && pq[p] > pq[i]) {
        swap(pq[p], pq[i]);
        
        i = p;
        p = (i-1)/2;
    }
}
int pop(vector<int>& pq) {
    auto ans = pq[0];
    
    pq[0] = pq.back();
    pq.pop_back();
    
    int i = 0;
    while(1) {
        int l = i*2+1;
        
        if (l >= pq.size())
            break;
        
        int t = i;
        if (pq[t] > pq[l])
            t = l;
        
        int r = l+1;
        if (r < pq.size() && pq[t] > pq[r])
            t = r;
        
        if (t == i)
            break;
        
        swap(pq[i], pq[t]);
        i = t;
    }
    
    return ans;
}

int solution(vector<int> scoville, int K) {
    vector<int> pq;
    for (auto s : scoville)
        push(pq, s);
    
    int count = 0;
    while(pq[0] < K) {
        if (pq.size() == 1) {
            return -1;
        }
        auto a1 = pop(pq);
        auto a2 = pop(pq);
        push(pq, a1+a2*2);
        count++;
    }
    
    return count;
}