프로그래머스 더 맵게 - C++, priority_queue로 min_heap 구성

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

 

첫 번째로 풀었던 방식.

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
bool isComplete(vector<int> sco, int K){
    for(auto s : sco){
        if(s<K) return false;
    }
    return true;
}
 
void makeSco(vector<int> &sco){
    int min1 = sco[0];
    int min2 = sco[1];
    int mix = min1 + (min2*2);
    sco.erase(sco.begin());
    sco[0] = mix;
}
 
int solution(vector<int> scoville, int K) {
    int first = scoville.size();
    int answer = 0;
    while(!isComplete(scoville, K)){
        sort(scoville.begin(), scoville.end());
        makeSco(scoville);
        answer++;
        if(scoville.size()==1&& !isComplete(scoville, K)){
            answer=-1;
            break;
        }
    }
    return answer;
}

시간초과 남 ㅠㅠ 매 반복문마다 추가하고 정렬하고, 검사해서 그런듯하다.

쓸데없이 반복문을 너무 돌았음..ㅎ

 

그래서 넣기만 하면 자동으로 정렬되는 자료구조인 priority_queue로 최소힙을 구성하고, 그에 맞는 로직으로 변경함.

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
void makeSco(priority_queue<int,vector<int>, greater<int>> &pq){
    int min1 = pq.top();
    pq.pop();
    int min2 = pq.top();
    pq.pop();
    int mix = min1 + (min2*2);
    pq.push(mix);
}
 
int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int,vector<int>, greater<int>> pq(scoville.begin(), scoville.end());
    while(pq.top()<K){
        makeSco(pq);
        answer++;
        if(pq.size()==1 && pq.top()<K){
            answer=-1;
            break;
        }
    }
    return answer;
}

굳이 반복문을 여러개 쓰지 않아도, 조건 검사를 할 수 있었다.

priority_queue를 선언할 때, greater<int>를 사용하여 오름차순으로 정렬되도록 하였고, (scoville.begin(), scoville.end())로 초기화 하였음!!(참고, 배열일때는 (arr, arr+arr.size())로 하면 되는 듯하다.)

 

짠