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

문제 설명

스코빌 지수를 나열한 int 배열이 주어진다. 그 배열에서 "특정 스코빌 지수" 2개를 차례대로 꺼내어(=삭제) 이 식에 대입한다; 가장 적은 스코빌 지수 + (그 다음으로 적은 스코빌 지수 * 2). 그 후 이 식으로부터 도출된 값을 다시 그 배열에 넣는다(=추가). 만일 이 배열 내에 있는 모든 스코빌 지수가 K보다 커진다면 이 과정을 종료한 뒤, 몇 번이나 "꺼내고 넣는" 과정을 반복해야 했는지, 그 횟수를 return한다.

 

입출력 예

scoville = { 1, 2, 3, 9, 10, 12 }

K = 7

결과 : 2

 

그 이유는?

1회차 : 1 + (2 * 2) = 5, --> scoville = { 3, 5, 9, 10, 12 }

2회차 : 3 + (5 * 2) = 13, --> scoville = { 9, 10, 12, 13 }

2회차를 거친 이후엔, 배열 내의 모든 scoville 지수가 K값인 7보다 크다.

 

제한사항 분석

문제에서 주어진 바로는...

scoville의 길이는 2 이상 1,000,000 이하입니다.

K는 0 이상 1,000,000,000 이하입니다.

scoville의 원소는 각각 0 이상 1,000,000 이하입니다.

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

이러한 조건들이 있다. 

 

1. 만일 스코빌 배열의 길이가 2 이상이라는 조건이 없었다면 배열의 길이를 선제적으로 체크하기 위해 do-while문으로 짰겠지만, 그렇지 않았기에 while문으로 했다.

2. K값의 범위는 0 ~ 1,000,000,000인데, max값이 10^9이므로 int로 해도 된다.

3. 이것도 딱히 문제가 되진 않는다.

4. 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우는 --> 배열 내의 원소의 크기가 모두 K 미만이면서, 원소의 개수가 2 미만일 때이다.

 

그러나 다른 문제와는 다르게 따로 제한사항 분석을 적은 이유는, 한 가지 오류를 생각해낼 수 있기 때문이다. 

만일 K가 10^9인 경우에, 일련의 과정을 통해, 배열 내에 원소가 2개가 남았고, 각각의 원소가 10^9 - 1과 10^9라고 하자. 이런 경우, 모든 원소가 K값 이상이 아니므로 10^9 - 1 + (2 * 10^9)를 한 값을 배열에 넣을 것이다. 그러면 int 오버플로우가 난다. 이렇게 되면 배열 내에 남는 원소는 오롯이 "음수"가 되며, 이는 "모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우"가 된다. (원래는 가능한 경우이다)

 

이러한 문제를 해결하기 위해선 long long을 사용해야 할 것이다.

 

풀이

최소 힙(우선순위 큐)을 사용하는 문제이다.

 

1. scoville 배열에 있는 값들을 차례로 읽어 최소 힙에 넣는다.

 

2. 최소 힙의 맨 위에서 2개의 원소를 읽어서 최솟값들을 구한 뒤, 문제에 나온 식에 따라 연산을 하고, 그 결과를 push를 한다. 물론 사용한 최솟값들은 pop한다.

 

3. 만일 배열 내의 모든 원소가 K 이상이라면 종료하고, (이때, 굳이 O(n)을 소모해서 모든 원소와 K값을 대조할 필요는 없다. 최소 힙이므로 top값만 K와 대조하면 된다)

 

4. 모든 원소가 K 이상이 아닌데, 배열 내의 원소의 개수가 2개 미만이라면 -1을 return한다.

 

코드

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

using namespace std;

int solution(vector<int> scoville, int K)
{
    priority_queue<int, vector<int>, greater<int>> mh; // 최소 힙
    for (int i = 0; i < scoville.size(); i++)
        mh.push(scoville[i]);

    int work_count = 0;
    int first, second;
    while (true)
    {
        if (mh.top() >= K) 
        {
            return work_count;
        }
        else if (mh.size() < 2)
        {
            return -1;
        }
        else
        {
            first = mh.top(); mh.pop();
            second = mh.top(); mh.pop();
            mh.push(first + second * 2);
            work_count++;
        }
    }

    return -2; // 절대 발생하면 안 되는 경우
}

int main(void)
{
    vector<int> scoville = { 1, 2, 3, 9, 10, 12 };
    int K = 7;
    cout << solution(scoville, K);
}