[Programmers Level2] 더 맵게(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회입니다.

 

 

[문제 풀이]

 

 

입출력 예 설명을 보고 이 문제는 우선순위 큐(priority queue)를 사용해야겠다고 생각했다.

 

그렇게 생각한 이유는

초기 scoville 순서는 {1, 2, 3, 9, 10, 12} 이고,

1회 섞은 후에는 순서가  {5, 3, 9, 10, 12} 된다.

 

만약 우선 순위 큐(최소힙)를 사용하면

섞은 후에 다른 추가적인 정렬 작업을 하지 않아도 힙의 구조상 scoville 순서가 {3, 5, 9, 10, 12} 가 되기 때문이다.

 

예를 들어서 코드를 설명하자면

 

파라미터로 주어진 vector의 scoville 값을 우선순위 큐에 옮긴다.

우선 순위 큐의 top을 num 변수에 저장한다.

 

 

1. 우선순위 큐가 비어있지 않을때, 우선순위 큐 사이즈가 1이 아닐때  두 조건을 모두 만족한다면

(두 조건을 만족하지 않는다면 while 반복문을 빠져나간다.)

 

2. num 값(우선 순위 큐 top)이 K보다 작을 때

(num 값이 K보다 크거나 같으면 while 반복문을 빠져나간다.)

우선 순위 큐 top 값을 빼준다.

 

3. 그리고 우선 순위 큐가 비어있는지 확인한다.

만약 비어있지 않다면

이전에 빼주었던 num과 우선 순위 큐의 top을

문제에서 주어진 공식에 의해 섞는다.

 

4. 섞은 후에

 

• 우선 순위 큐 top을 빼주었다.
• 섞은 결과를 우선순위 큐에 넣었다.
• num에 우선순위 큐의 top을 갱신해주었다.

 

위 과정(1 ~ 4)을 반복하고 while 반복문을 빠져나가게 되면

 

'모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.' 조건 때문에

우선 순위 큐의 top을 확인한다.

 

우선 순위 큐의 top이 K보다 작은 경우

모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우라 판단하여 answer를 -1로 값 변경을 했다.

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/Programmers: Study Programmers for Coding Test

 

 

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

    for (int element : scoville) {
        pq.emplace(element);
    }
    
    int num = pq.top();
    while (true) {
        if ((!pq.empty()) && (pq.size() != 1)) {
            if (num < K) {
                pq.pop();
                if (!pq.empty()) {
                    ++answer;
                    int result = num + (pq.top() * 2);
                    pq.pop();
                    pq.emplace(result);
                    num = pq.top();
                }
            }
            else {
                break;
            }
        }
        else {
            break;
        }
    }

    if (pq.top() < K) {
        answer = -1;
    }

    return answer;
}