[C++]프로그래머스 더 맵게(힙)

코딩테스트 연습 - 더 맵게 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

이 문제는 매 포문을 실행할 때마다 스코빌이 오름차순으로 새로 정렬되어야 한다.

또한, 가장 앞쪽에 있는 값이 갱신 된 후에 오름차순 정렬이 이루어져야 한다.

이러한 두가지 조건에 모두 적합한 자료구조가 바로 '힙'이다.

C++에서는 heap이라는 이름 대신 priority_queue로 이루어져있다.

queue와 비슷하지만 front()대신 top(), 매번 push할때마다 정렬이 되는 구조이다.

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

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int, vector<int>, greater<int>> scov; //heap을 의미, 자동 오름차순정렬되는 queue (그냥 <int>면 내림차순 정렬한다. 복잡하지만 외워야함.)
    for(int i = 0; i < scoville.size(); i++)
        scov.push(scoville[i]);
    for(int i = 0; i < scoville.size(); i++)
    {
        if(scov.top() < K)
        {
            int temp = scov.top();
            scov.pop();
            scov.push(temp + scov.top() * 2);
            scov.pop();
            answer++;
        }
        else
            return answer;
    }
    return -1;
}

priority_queue를 오름차순 정렬하고 싶을 때는

priority_queue<int, vector<int>, greater<int>>로 선언해야 하며, 이는 외우는 것이 좋다.

 

그때그때 top이 K보다 작은지만 판별하면, 힙에서는 자동으로 top기준으로 오름차순으로 정렬해주므로 바로 모든것이 조건을 만족했는지 판별이 가능하다.

 

또한, pop이후 push를 해주면 abort 오류가 뜰 수 있기 때문에 push이후 pop을 해주는 것이 좋다.