JArchive 프로그래밍 일기

문제

더 맵게 프로그래머스 level2

리뷰

힙 카테고리에 있는 문제다.

처음에는 내림차순으로 정렬 후, 뒤에서 첫번째, 두번째 숫자들을 pop_back, 새로 계산한 숫자를 push_back 해서 해결하려고 했었다.

하지만 자꾸 (비용이 큰 함수) sort()를 해야 해서 "실패" 떴다. 그리고 벡터 크기가 2 이상인지도 체크도 안해줬다...

실패한 코드

#include <functional> 

int solution(vector<int> scoville, int K) {
    int answer = 0;
    int last = scoville.size()-1;

    while(scoville[last] >= K){

        sort(scoville.begin(), scoville.end(), greater<int>()); // 내림차순 
        last = scoville.size()-1;
        int new = scoville[last-1]*2 + scoville[last];
        scoville.pop_back();
        scoville.push_back(new);

        answer++;
    }

    return answer;
}

힙 을 사용해서 바꿨다.

priority_queue<int, vector<int>, less<int> > pq; // 오름차순
priority_queue<int, vector<int>, greater<int> > pq; // 내림차순

내림차순으로 정렬한 우선순위 큐를 선언하고, 벡터의 원소를 모두 넣는다.

맨 위에는 가장 작은 값이 오니까 2개 꺼내서 새 값을 계산해서 다시 푸시한다.

이 때, 2개를 꺼내야 하니까, 큐의 사이즈가 1인지 확인하여 예외처리를 해준다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
using namespace std;

int solution(vector<int> scoville, int K) {
    priority_queue<int, vector<int>, greater<int> > pq;
    int answer = 0;

    for(int i=0; i <scoville.size(); i++){ // 벡터 원소를 모두 큐에 넣는다 
        pq.push(scoville[i]);
    }

    while(pq.top() < K){

        if(pq.size() < 2){
            answer = -1; break;    
        } 

        int top = pq.top();
        pq.pop();
        int second = pq.top();
        pq.pop();

        pq.push(second*2 + top);
        answer++;
    }

    return answer;
}