[프로그래머스/C++] 더 맵게

(5/19) - O

구현

priority_queue를 이용해서 풀었다. 특징이랑 내장 함수는 잘 모르는데, 원소들을 우선순위로 계속 정렬해 간다는 것만 알아서 선택했다. 근데 왜 int 하나로 독자적으로 만들어지지 않고 두 번째 타입으로 vector<int>를 넣어 줘야 컴파일 되는 걸까?.. key-value 쌍을 원소로 취하는 자료구조인가?....ㅎㅎ 긴가민가하면서 풀었다

priority_queue에 스코빌 지수들을 담는다. 내림차순이 default이므로 greater로 지정해 준다.

맨 앞의 두 원소가 가장 안 매운 스코빌 지수, 그리고 두 번째로 안 매운 스코빌 지수이기 때문에, top() 저장-pop()을 두 번 해 주면 된다. 이 둘을 섞어 준다.

섞은 스코빌 지수를 다시 priority_queue에 담는다.

맨 앞의 원소가 목표 스코빌 지수 K보다 크다면 그 다음 이어질 원소들도 K보다 클 것이다. 섞기를 중지하고 섞은 횟수를 return 한다.

 

Priority_queue

https://chae-d-2.tistory.com/156

std::priority_queue

 

 

코드

#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;
    for (const int& i : scoville) {
        pq.push(i);
    }

    int mix_cnt = 0;

    while (true) {
        int des = pq.top();
        pq.pop();
        int src = pq.top();
        pq.pop();
        int mix_result = des + (src * 2);
        pq.push(mix_result);
        mix_cnt++;

        if (pq.top() >= K) {
            answer = mix_cnt;
            break;
        }
        if (pq.size() == 1 && pq.top() < K) {
            answer = -1;
            break;
        }
    }
    return answer;
}