[ 프로그래머스 ] 더 맵게

문제

---

https://school.programmers.co.kr/learn/courses/30/lessons/42626

풀이

---

주어진 배열의 모든 원소가 K 이상이 될 때까지 반복하여 연산을 진행 시, 이를 위해 필요한 최소 횟수를 구하는 문제이다. 따라서 배열을 priority_queue를 통해 오름차순으로 정렬하고 K 이하의 원소 두 개를 연산하여 새로운 숫자를 만들어, queue에 넣는 것을 반복한다. 이를 맨 앞 원소가 K이상이 될 때까지 반복하고 카운트하여 return한다.

#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>> p_qu_g;

    for (int i = 0; i < scoville.size(); i++)
    {
        p_qu_g.push(scoville[i]);
    }

    int cnt = scoville.size();
    while (cnt--)
    {
        if (p_qu_g.size() < 2)
        {
            if (p_qu_g.top() >= K)
            {
                return answer;
            }

            break;
        }

        if (p_qu_g.top() < K)
        {
            int new_sco = 0;
            new_sco += p_qu_g.top();
            p_qu_g.pop();
            new_sco += (p_qu_g.top() * 2);
            p_qu_g.pop();

            p_qu_g.push(new_sco);
            answer++;
        }

        else if(p_qu_g.top() >= K)
        {
            return answer;
        }
    }

    return -1;
}