알고리즘(C++) / 프로그래머스 level 2 : 더 맵게

level 2 : 더 맵게

https://programmers.co.kr/learn/courses/30/lessons/42626?language=cpp 

코딩테스트 연습 - 더 맵게

 

코드

//프로그래머스 더 맵게
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

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) {
        if (pq.size() < 2) {
            answer = -1;
            break;
        }
        int a = pq.top(); //가장 맵지 않은 음식
        pq.pop();
        int b = pq.top(); //두 번째로 맵지 않은 음식
        pq.pop();
        pq.push(a + (b * 2)); //섞은 음식
        answer++; //섞은 횟수
    }
    return answer;
}

int main() {
    vector<int> scoville = { 1,2,3,9,10,12 };
    int K = 7;
    cout << solution(scoville, K) << "\n";
    return 0;
}

 

설명

우선순위 큐 선언한다. 우선순위 큐는 힙 알고리즘으로 구현되어있고 오름차순으로 선언한다.

더이상 섞을 음식이 없고 K보다 지수가 작다면 반복문을 빠져나온다. 

우선순위 큐에 가장 맵지 않은 음식과 두번째로 맵지 않은 음식에 *2한 값을 push한다.

반복문을 한 번 반복할 때마다 answer을 증가한다. 

 

고찰

이번 문제는 정확성과 효율성 문제 모두 통과해야한다. 

하지만 vector, erase로는 정확성은 만족시킬수있지만 효율성을 만족시키지 못한다. 그래서 힙으로 구현되어있는 priority_queue를 사용하여 문제를 풀 수 있다. 

priority_queue

//우선순위 큐 내림차순 정렬(default)
priority_queue<int> pq(scoville.begin(), scoville.end());
//우선순위 큐 오름차순 정렬
priority_queue<int, vector<int>, greater<int>> pq(scoville.begin(), scoville.end());