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

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

더 맵게

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

코딩테스트 연습 - 더 맵게

문제

매운 것을 좋아하는 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의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

 

풀이

입출력 예시

 

풀이

스코빌 지수를 담아줄 최소 힙을 하나 지정해주자. 연산은 작은 스코빌 지수에서 일어나기 때문이다. 그곳에는 입력받을 스코빌 지수들을 넣어주자.

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

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int, vector<int>, greater<int>> mix; // 우선순위 큐. 오름차순으로 저장.
    
    for (const auto& s : scoville) {
        mix.push(s);
    }
    
    return answer;
}

이후 스코빌 지수가 K보다 낮을 때마다 첫번째 스코빌 지수 + 두번째 스코빌 지수 x 2 를 해주자. 단, 힙의 크기가 1이면 더 이상 연산할 수 없기 때문에 -1를 반환해주도록 하자.

...
    ...
    while (true) {
        int tempK = 0;
        if (mix.top() < K && mix.size() >= 2) {
            tempK = mix.top();
            mix.pop();
            tempK += mix.top() * 2;
            mix.pop();
            mix.push(tempK);
            answer++;
        }

        if (mix.top() >= K) {
            return answer;
        }
        else if (mix.size() == 1) { // 더 이상 연산을 할 수 없으므로 -1을 반환
            return -1;
        }
    }
}

전체 코드

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

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int, vector<int>, greater<int>> mix; // 우선순위 큐. 오름차순으로 저장.
    
    for (const auto& s : scoville) {
        mix.push(s);
    }

    while (true) {
        int tempK = 0;
        if (mix.top() < K && mix.size() >= 2) {
            tempK = mix.top();
            mix.pop();
            tempK += mix.top() * 2;
            mix.pop();
            mix.push(tempK);
            answer++;
        }

        if (mix.top() >= K) {
            return answer;
        }
        else if (mix.size() == 1) { // 더 이상 연산을 할 수 없으므로 -1을 반환
            return -1;
        }
    }
}

결과

효율성 테스트가 있었지만, 무사히 통과했다.