[프로그래머스] 레벨2 - 더 맵게

코딩테스트 연습 - 더 맵게

문제 설명

scoville 벡터 (얼마나 매운지를 나타내는 값)와 K를 입력받을 때, scoville 벡터의 모든 값이 K 이상이어야 한다. 그럴려면 scoville 벡터를 섞어야 하는데 섞는 방법은

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

이다.

최소한으로 섞어서 모든 scoville 벡터의 element가 K이상이 되도록 하는 횟수를 구하는 문제이다.

풀이

scoville의 자료구조를 vector가 아닌 priority_queue로 해야 한다. (문제에선 vector로 입력 받는다.)

왜냐하면 섞은 음식의 스코빌 지수 를 scoville에 재정합 해야되는데 벡터에선 그게 쉽지 않다.

그러므로 최소 우선순위 큐를 사용해야 한다.

코드

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<ll, vector<ll>, greater<ll>> pq_sco;
    
    // pq_sco에 스코빌 지수 push
    for (auto e : scoville)
    {
        pq_sco.push((ll)e);
    }
    
    while(1)
    {   
        // upper k check
        if (pq_sco.top()>=K)
            break;
        // fail check
        if (pq_sco.size() < 2)
            return -1;
        
        
        ll small = pq_sco.top();
        pq_sco.pop();
        ll big = pq_sco.top();
        pq_sco.pop();
        pq_sco.push(small + big * 2);
        
        answer++;
    }
    
    return answer;
}

소감

priority_queue<ll, vector<ll>, greater<ll>> pq;

이 구조를 잘 기억하자. 코딩테스트를 하다가 reference를 보지 못할 수도 있기 때문이다.

참조

[프로그래머스] 레벨3 - 디스크 컨트롤러