프로그래머스 (더 맵게, 힙(Heap)) C++

 

// 기본적으로 만들어지는 큐가 내림차순 정렬이 된다.
Priority_queue <int> pq;

// 오름차순으로 벡터를 정렬할 때
Priority_queue<int, vector<int>, greater<int>> pq;

// 우선순위 큐의 원소 삽입
pq.push(원소);

// 우선순위의 가장 앞의 원소 확인
pq.top();

// 우선순위의 가장 앞의 원소 제거
pq.pop();

// 크기 확인 및 비어있는지 유무
pq.size();
pq.empty();

 

우선순위 큐를 쓰지 않고는 정답처리가  되지 않는 문제였다. 기존에는 sort를 이용해서 while 문 안에서 계속적으로 정렬을 시켜줬는데 이는 효율성 측면에서 좋지 않음을 배울 수 있었다. priority_queue를 선언하면 오름차순으로 자동 정렬되고 이를 이용해 top확인pop 제거 push 추가를 한다면 더욱이 효율적인 코드가 될 것이다.

 

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

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    
    priority_queue <int, vector<int>, greater<int>> p_queue (scoville.begin(), scoville.end());
    
    while(p_queue.size() > 1 && p_queue.top() < K) {
        int first = p_queue.top();
        p_queue.pop();
        
        int second = p_queue.top();
        p_queue.pop();
        
        int new_sco = first + second * 2;
        p_queue.push(new_sco);
        
        answer++;
    }
    
    if(p_queue.top() < K) return -1;
    
    return answer;
}

 

 

이는 내가 우선순위 큐를 사용하지 않았을 때 테스트 케이스를 통과한 코드이다

 

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    int new_sco = 0;
    
    while(true) {
        int count = 0;
        
        for(int i = 0 ; i < scoville.size() ; i++) {
            if(scoville[i] >= K) count++;
        }
        
        if(count == scoville.size()) break;
        
        sort(scoville.begin(), scoville.end());
        
        new_sco = scoville[0] + scoville[1] * 2;
        scoville.erase(scoville.begin());
        scoville[0] = new_sco;
        
        
        answer++;
    }
    
    return answer;
}