[프로그래머스] 더 맵게 / 힙(Heap) c++

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

프로그래머스

최소 힙을 이용하는 문제였다.

보자마자 최소힙이 생각났는데 선언방법을 까먹어서 구글링했다. 코테에서 나왔으면 못풀었을것같다.

자료구조 문제를 많이 풀지 않다보니 계속 까먹는다. 복습해야겠다.

우선순위 큐는 다음과 같이 선언할 수 있다. 

기본적인 자료형인 int 형을 원소로 쓰고 최대힙으로 하려면 아래처럼 생략해도 된다.(디폴트 : 최대힙)

priority_queue<int> pq;  // - >  priority_queue<int, vector<int>, less<int>> pq;

최소힙으로 하려면 아래와 같이 선언해주면 된다.

priority_queue<int, vector<int>, greater<int>> up;

• 우선순위 큐에  구조체나 클래스가 들어갈 수 있다. 
  그럴떄 구조체 내부의 비교 연산자 오버로딩 부분을 다음과 같이 작성하면 구조체의 멤버변수로 우선순위큐의 우선순위를 결정할 수 있다.

bool operator<(const Object& Obj)const { 

		return a < Obj.a;
	}

 

• 우선순위 큐 3번째 인자는 <우선순위를 결정하는 방법을 정희한 구조체>인데 이를 직접 작성할 수 있다.

//T는 구조체

struct cmp {
    bool operator()(T a, T b) {
        return a.id < b.id;
   }
};


//선언
priority_queue <T,vector<T>,cmp> pq;

풀이

1.우선 순위 큐에 스코빌지수를 오름차순으로 저장

2. 최소 스코빌 지수와 두 번째로 작은 스코빌 지수를  꺼내서 새로운 스코빌 지수를 만들어준다.
   2-1.   최소 스코빌 지수가 k보다 크면 모든 음식이 k이상의 스코빌 지수가 되는 것이므로
         반복문을 탈출하여 답을 출력한다.
   2-2.    2-1번 후 최소 스코빌 지수를 꺼냈는데 큐에 남아있는 스코빌 지수가 없으면 모든 음식의 스코빌 지수를
          K 이상으로 만들 수 없는것이므로 반복문을 탈출하여 -1을 출력해준다. 
  

#include <string>
#include <vector>
#include<queue>
using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    int size=scoville.size();
    priority_queue<int, vector<int>, greater<int>> up;
    while(size--)
        up.push(scoville[size]);
    int min=0,min2=0,mix;
    while(true)
    {
        min=up.top();
        if(min>=K)
            break;
        up.pop();
        if(up.size()==0)
        {
            answer=-1;
            break;
        }
        min2=up.top();
        up.pop();
        mix=min+min2*2;
        up.push(mix);
        answer++;
        
    }
        
        
    
    return answer;
}