[프로그래머스] Level.2 힙(heap)- 더 맵게

코딩테스트 연습 - 더 맵게

 

문제설명

제한사항

입출력예

 

첫번째 풀이 -정확성테스트 통과 ,효율성 테스트 실패

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

int solution(vector<int> scoville, int K) {
    int answer = 0;
    int num=0,mix=0;
    while(1){
        sort(scoville.begin(),scoville.end());
        if(K<=scoville.front()||scoville.size()==1) break;
        else {
            num++;
            mix=scoville[0]+2*scoville[1];
            scoville.push_back(mix);
            scoville.erase(scoville.begin(),scoville.begin()+2);
            if(scoville.size()==1&&scoville.front()<K) num=-1;
        }
    }
    answer=num;
    return answer;
}

 

두번쨰 풀이 -통과 ㅠㅠ

 

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

int solution(vector<int> scoville, int K) {
    int answer=0,num=0,mix=0;
    priority_queue<int, vector<int>, greater<int>> q;
    for(int i=0;i<scoville.size();i++)
        q.push(scoville[i]);
    while(1){
        if(K<=q.top()||q.size()==1) break;
        else {
            num++;
            int a=q.top();q.pop();
            int b=q.top();q.pop();
            mix=a+b*2;
            q.push(mix);
            if(q.size()==1&&q.top()<K) num=-1;
        }
    }
    answer=num;
    return answer;
}

 

일단 문제 카테고리부터..힙이였다..힙..................

일단 기본 아이디어는 오름차순으로 정렬했을때 첫번째 요소의 스코빌지수가 K이상이면  그 이후의 요소들도

스코빌 지수를 만족한다. 스코빌지수를 만족시키기 위해 섞었을때 스코빌지수는 가장 첫번째로 큰 스코빌지수와 그 다음번쨰 큰 스코빌 지수를 알기 위해 정렬이 필요하다..나는 그래서 sort를 반복했다. 하지만 그럼 시간 초과다..

 

c++에 우선순위 큐를 이용해서 최소힙을 구현해야한다.

최소힙을 이용하면 따로 정렬해줄 필요가 없다....

오름차순으로 정렬하는 이유는 최소힙의 첫번째요소 top이 가장 작은 숫자이기 때문이다!!!!

priority_queue<int, vector<int>, greater<int>> minHeap(v.begin(), v.end());

저 문제에서는 priority_queue<int,vector<int>,greater<int>> pq (scoville.begin(),scoville.end()); 이렇게 활용해주면 된다.