[알고리즘]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 합니다.

 

입출력 예

scovilleKreturn

[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회입니다.

 

구현방법

 

- 처음에는 배열을 sort를 이용해서 오름차순으로 정리하면서, 배열의 첫번째 원소 ( 가장 작은 원소 ) , 두번째 원소 ( 두번째로 작은 원소 ) 를 조합해서 배열에 추가하고, 두개의 원소는 지우는 식으로 진행

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int solution(vector<int> scoville, int K) {
	int answer = 0;
	int flag = 0;
	while (true) {
		flag = 0;
		sort(scoville.begin(), scoville.end());
		if (scoville[0] > K) return answer; // 다 큰 경우
		if (scoville.size()==2 && (scoville[0]+scoville[1]*2<K)) return -1;
		scoville.push_back(scoville[0] + scoville[1] * 2);
		scoville.erase(scoville.begin(), scoville.begin() + 2);
		answer++;
	}
	return answer;
}

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

	cout << solution(scoville, K) << endl;
}

-> 정답은 맞지만 시간초과 !

 

- 계속 오름차순으로 정렬되어있어야하는 점을 이용해서 우선순위 큐를 사용해보자 !

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;


int solution(vector<int> scoville, int K) {
	int answer = 0;
	int num = 0;
	priority_queue<int,vector<int>,greater<int>> sco; // 오름차순정렬 -> 최소힙
	for (int i = 0; i < scoville.size(); i++) sco.push(scoville[i]);
	while (true) {
		if (sco.top() >= K) break;
		if (sco.size() < 2 && sco.top() < K) return -1;
		num = sco.top();
		sco.pop();
		num = num + sco.top() * 2;
		sco.pop();
		sco.push(num);
		answer++;
	}
	return answer;
}

통과!!!!!