프로그래머스 - 더 맵게 < Level 2 >

문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

 

풀이

사용 언어 : C++

#include <vector>
#include <queue>       //큐 선언해준다

using namespace std;

int solution(vector<int> scoville, int K) 
{
 
    int first = 0;  //가장 맵지 않은 것
    int second = 0;  //두 번째로 맵지 않은 것

    int count = 0;   //섞은 횟수

    priority_queue<int, vector<int>, greater<int>>temp; //오름차순으로 정렬하기

    for (int i = 0; i < scoville.size(); i++) //백터에 있는 원소를 전부 큐에 넣는다
    {
        temp.push(scoville[i]);
    }


    while(temp.top() <= K && temp.size() > 1) //while문을 돌리는 조건은 모든 원소가 K이하일 때, 큐에 하나라도 원소가 있을 때
    {
        
        count++; //섞은 횟수 증가

        first = temp.top(); temp.pop(); //오름차순으로 정렬했으니 맨 뒤의 것이 가장 맵지 않은 것이 된다
        second = temp.top(); temp.pop(); //두 번쨰로 맵지 않은 것은 끝에서 두 번째 것
        temp.push(first + (second * 2)); //섞는 공식으로 섞엉!

    }

    if (temp.top() < K) //K보다 작은 것이 남아있을 수 밖에 없으면 -1 반환 하랬으니 반환
    {
        return -1;
    }
    else //다 K보다 작으면 섞은 횟수를 반환
    {
        return count;
    }
  

}