[힙(heap)] 더 맵게

<문제>

<문제 풀이>

(생각의 흐름)

1. 스코빌은 정리가 된 채로 오는가?
2. 스코빌을 섞었을 때 합해진 값은 항상 가장 맵지 않은 음식의 스코빌 인덱스가 바뀌는 가
3. sort를 써야하는가?
4. -> heap 자료구조를 사용하면은 1~3번은 신경쓰지 않아도 되겠다.
5. 최소 heap 자료구조에다가 스코빌의 원소를 모두 집어넣고,
6. (반복문_힙이 empty할 때 까지) 힙에서 2개의 수를 꺼내(pop)면 "가장 작은 수와 그 다음 작은 수"가 두 개 나오겠지 first가 K값을 넘는지 확인하고 넘지 않으면 공식에 따라 곱셈과 덧셈을 한다. (K값을 넘는다면 중지.)
7. 그다음에 K값을 넘으면 MIX값 증가시키고, 다시 집어넣는다. K값 넘지 않으면 MIX값을 증가시키지 않고 집어넣는다
8. 모든 과정이 끝났을 때 first가 k보다 작다면 ANSWER는 -1을 리턴한다.

조만간 heap 자료구조에 대하여, 그리고 stl사용법에 대해 정리 한번 하자!

 

<코드 구현>

-내 풀이

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

using namespace std;



int solution(vector<int> scoville, int K) {
    int answer = 0;
    int first = 0, second = 0, s_index=0, mix= 0;

    
    priority_queue<int, vector<int>, greater<int>> pq;
    
    
    for(int elem : scoville) {
        pq.push(elem);
    }
    
    while(!pq.empty()) {
        first = pq.top();
        pq.pop();
        
        if(pq.empty() || first >= K ) 
            break;

        second = pq.top();
        pq.pop();
        
        s_index = first + (second * 2);
        mix++;
        pq.push(s_index);
    }
    
    if(first < K) answer = -1;
    else answer = mix;
    return answer;
}

 

-다른 사람 풀이

#include <vector>
#include <queue>
using namespace std;
int solution(vector<int> scoville, int K) {
    int answer = 0;
    int needHot;
    priority_queue<int,vector<int>,greater<int>> pq (scoville.begin(),scoville.end());
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++;
    }
return answer;
}

 

출처 http://<https://programmers.co.kr/learn/courses/30/lessons/42626/solution_groups?language=cpp>

진짜 너무 깔끔;; 

우선 priority_queue를 정의하면서 scoville을 초기화 해준 거? 섹시함.

그리고 while문 조건을 empty로 한 것이 아니라 pq.top()<K 로 해서, 안에서 추가로 끝나는 조건을 pq.size()==1 일 때로 하면 코드 완전 많이 줄일 수있음. 멋있음.

또 굳이 second를 뽑지않고 pq.top()*2해서 최적화 한거? 아주 깔끔해 배우자!