[알고리즘문제] 프로그래머스 - 더 맵게

문제는 크게 어렵지 않은데, 처음 문제를 읽었을 때 바로 이해가 되지 않았다. 문제를 2번 읽고, 입출력 예 설명을 읽고 문제를 이해할 수 있었다.

 

스코빌 지수가 나오고 하는데, 문제를 쉽게 설명하면 배열에 자연수가 들어가 있다.

배열에서 첫번째, 두번째로 작은 값을 꺼내고 첫번째 + (두번째 * 2)값을 다시 배열에 넣는다. 이 과정을 한번 연산을 진행했다고 말한다.

결과는 위의 연산을 몇번 진행을 해야 배열의 모든 값이 K이상이 되는가? 묻는 문제이다.

 

첫번째, 두번째로 작은 값을 꺼내야 하기 때문에 min heap을 사용하였다. min heap에서 값을 꺼내면 가장 작은 값이 나오기 때문.

 

while문의 조건은 초기 heap.size() > 1인데, 그 이유는 한번의 연산을 하면서 heap에서 값이 하나씩 없어지기 떄문에(2번 pop, 한번 push) heap에 원소가 하나 있으면 더이상 연산을 할 수 없기 때문이다.

 

이후의 코드는 heap에서 두개의 원소를 꺼내 문제에서 제시한 연산방법으로 계산을 하고 결과값을 다시 넣는다. 그리고 heap의 top, 즉 heap의 최소값이 k보다 크거나 같으면 heap의 모든 원소가 k보다 크거나 같음을 의미하기 때문에 연산횟수를 return 한다.

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;


int solution(vector<int> scoville, int K) {
    
    priority_queue<int, vector<int>, greater<int> > heap(scoville.begin(),scoville.end());
    int answer = 0;
    
    
    int size = heap.size()-1;
    
    while(heap.size() > 1){
        
        int num1 = heap.top();
        heap.pop();
        int num2 = heap.top();
        heap.pop();
        
        int cal = num1 + (num2 * 2);
        heap.push(cal);
        
        answer++;
        
        if(heap.top() >= K){
            return answer;
        }
    }
    
    return -1;
}