[레벨 2] 더 맵게

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

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int,vector<int>,greater<int>> pq;
    int len = scoville.size(),i;
    
    
    for(i = 0; i < len; ++i)
        pq.push(scoville[i]);
        
    int scovilleTop = pq.top();
    if(scovilleTop >= K)
        return answer = -1;
        
    while(true)
    {
        int firstSco = pq.top();
        pq.pop();
        int secondSco = pq.top();
        pq.pop();
        if(firstSco >= K)
            break;
        else
        {
            int res = firstSco + (secondSco * secondSco);
            pq.push(res);
            ++answer;
        }
    }
    if(answer == 0)
        answer = -1;
    
    return answer;
}

처음에 접근한 방식.

스코빌지수를 최소힙에 담은다음. 최소힙의 구조(루트노드가 가장작음. 빼낸다해도 그 다음 작은 노드가 들어온다)

를 이용하여 firstSco와 secondSco를 구하는 방식으로 접근.

 

fail이 뜸.

 

왜 안되지를 한참고민하다 문제를 잘못읽었다.

두 번째로 맵지 않은 음식의 스코빌 지수 * 두 번째로 맵지 않은 음식의 스코빌 지수가 아닌

두 번째로 맵지 않은 음식의 스코빌 지수 * 2였다.

그리고 스코빌 지수의 -1의 케이스 -> 더해도 K를 넘지못하는 케이스를 따로 넣지않음.

 

문제는 통과한 밑의 코드

 

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

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int, vector<int>, greater<int>> pq;
    int len = scoville.size(), i;
    for (i = 0; i < len; ++i)
    {
        pq.push(scoville[i]);
    }

    int scovilleTop = pq.top();
    if (scovilleTop >= K)
        return answer = -1;
    while (true)
    {
        int firstSco = pq.top();
        pq.pop();
        if (firstSco >= K)
            break;
        int secondSco = pq.top();
        pq.pop();
        // 사이즈가 0인상태.
        if (pq.size() <= 0)
        {
            if (firstSco + (secondSco * 2) < K)
                return answer = -1;
        }
        int res = firstSco + (secondSco * 2);
        pq.push(res);
        ++answer;
    }

    return answer;
}

 

다른 사람의 코드를 볼때,

while(pq.top()<K) {
    if(pq.size()==1) return answer = -1;
    needHot=pq.top(); pq.pop();
    pq.push(needHot+pq.top()*2);
    pq.pop(); answer++;
}

 

 

 

결국 힙의 size가 1까지 줄어든단 의미는 K지수를 못넘기기에 계속 진행되었던것이고

(만약 그렇지않다면 더해지는 과정에서 힙의 루트노드를 확인할 때, K지수를 넘겼기에(원소가 몇개남아있건 루트노드는 제일 작은 상태일테니.) 제대로 K지수를 모두 넘겼단 의미)

size가 1이면서 K지수를 못넘긴것은 힙의 원소들이 단 하나도 K를 못넘겼기에 -1을 리턴.