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

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

문제링크 : 더 맵게

코딩테스트 연습 - 더 맵게

 

문제설명

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

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

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

 

제한 사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

 

입출력 예

scoville	K	return
[1, 2, 3, 9, 10, 12]	7	2

입출력 예 설명

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]
2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
   가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

 

---

풀이과정

1. 오름차순 정렬을 계속 해주고 첫번째 값과 두 번째 값을 계속해서 계산해서 새롭게 컨테이너에 넣어주고 그 첫번째 두번째 값은 빼줘야 한다.
2. 따라서 큐에서 빼고 계산해서 넣어주면 된다.
3. 근데 큐에서 낮은 순서로부터 빼야하니까 우선순위 큐를 사용해야 한다.
4. 우선순위 큐는 c++ 에서는 STL 로 쉽게 구현이 가능하다. 관련 개념은 링크 : Heap, Priority Queue 개념 c++ 구현 를 들어가보자.

 

코드

#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

struct comp {
    bool operator()(int a, int b) {
        return a > b;
    }
};

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int, vector<int>, comp> pq;

    for(auto x : scoville) {
        pq.push(x);
    }

    while(true) {
        if(pq.size() < 2)
            break;

        int first = pq.top();
        if(first > K)
            break;
        pq.pop();

        int second = pq.top();
        pq.pop();

        int mix = first + (second * 2);
        pq.push(mix);

        answer++;
    }

    if(pq.top() < K)
        return -1;

    return answer;
}