프로그래머스 힙(Heap) 더 맵게

힙이란 ?

힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조
(위키백과)

힙(heap) 예시 그림

 

힙 구현 방법 :

힙을 리스트(배열)로 표현한것

 

 

---

문제 설명

매운 것을 좋아하는 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 합니다.

입출력 예

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

 

---

나의 알고리즘

첫번째 알고리즘 : 힙 자료구조를 사용하지 않고 프로그램을 작성해 보았다.

결과는 잘 나오지만 효율성에서 모두 시간초과가 나왔다.

---

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    vector<int> tmp = scoville;
    sort(tmp.begin(),tmp.end());	//오름차순 정렬
    while(tmp[0] < K){	//가장 작은것이 K보다 클때 정지한다.
    	if(tmp.size() < 2){ //더 이상 더할 수 없을 때 -1을 반환한다.
    		return -1;
		}
    	int t = tmp[0] + (2*tmp[1]); //가장 작은 2개의 수에 대해 계산을 한다.
    	tmp.erase(tmp.begin(),tmp.begin()+2); //백터에서 앞서 더한 2개의 수를 지운다.
    	tmp.push_back(t); //계산한 수를 백터에 넣는다.
    	sort(tmp.begin(),tmp.end()); //다시 정렬한다.
    	answer++; //횟수를 추가한다.
	}
    return answer;
}

---

 

다음으로 고안한 알고리즘이 우선순위 큐를 사용하여 작상한 알고리즘이다.

 

대략적인 알고리즘은 같고 기존 백터 정렬을 하던 부분을 올림차순 우선순위 큐를 사용하여 시간을 줄였다.

---

int solution(vector<int> scoville, int K) {
	int answer = 0;
	priority_queue<int, vector<int>, greater<int>> pq;
	for (auto i : scoville) {
		pq.push(i);
	}
	while (pq.top() < K) {//가장 작은것이 K보다 클때 정지한다.
		if (pq.size()< 2) { //더 이상 더할 수 없을 때 -1을 반환한다.
			return -1;
		}
		int n1 = pq.top();	//첫번쨰로 덜 매운 것을 가져온다.
		pq.pop();
		int n2 = pq.top();	//두번쨰로 덜 매운 것을 가져온다.
		pq.pop();
		int t = n1 + (2 * n2); //가장 작은 2개의 수에 대해 계산을 한다.
		pq.push(t); //계산한 수를 백터에 넣는다.
		answer++; //횟수를 추가한다.
	}
	return answer;
}

---

 결과는 성공이다.

 

 

 

---

다른 풀이 해석

 

#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    int needHot;
    priority_queue<int,vector<int>,greater<int>> pq (scoville.begin(),scoville.end());

    while(pq.top()<K) {
        if(pq.size()==1) return answer = -1;
        needHot=pq.top(); pq.pop();
        pq.push(needHot+pq.top()*2);
        pq.pop(); answer++;
    }

    return answer;
}

Curookie , - , 엄인섭 , 조혜민님의 풀이입니다.

---

배운점 

기존의 백터를  priority_queue에 직접적으로 넣을 수 있다는 사실을 알았다.

간단한 계산식이므로 push에 직접 식을 넣을 수 있다는 것을 깨달았다.

 

프로그래머스 문제를 풀어보며 점점 자신이 간단하게 코딩을 할 수 있게 되는 것 같아 뿌듯함을 느꼈다.