[알고리즘 풀이 분석] Programmers 더 맵게

더 이상 미룰 수 없을 때 까지 미룬,, 나의 알고리즘,, ㅎ,,
해결한 문제를 리뷰하며 더 좋은 풀이를 기반으로 나아질 점을 기록해보고자 한다!

Programmers 더 맵게

문제는 여기서 확인!
코딩테스트 연습 - 힙 - level 2

문제 목표

scoville 배열로 들어오는 모든 음식들의 스코빌 지수를 K 이상으로 만들기

입출력 예

제한 사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

나의 풀이

#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    int mixcount = 0;
    priority_queue<int, vector<int>, greater<int>> minHeap;
    
    for(int i=0; i<scoville.size(); i++){
        minHeap.push(scoville[i]);
    }
    
    while(!minHeap.empty()){
        if(minHeap.size() == 1){ 
            if(minHeap.top() < K) answer=-1;    // 불가능한 경우
            else answer = mixcount;
            break;
        }else{ //원소가 2개 이상
            if(minHeap.top() >= K){
                answer = mixcount;
                break;
            }
            int first = minHeap.top();
            minHeap.pop();
            int second = minHeap.top();
            minHeap.pop();
        
            int mixed = first + 2*second;
            minHeap.push(mixed);
            mixcount++;
        }
    }
    
    return answer;
}

문제 자체가 힙 카테고리에 속해 있었기에 쉽게 우선순위 큐 사용을 유추할 수 있었다. 모든 음식이 K 이상의 스코빌 지수를 자겨야 했기에 최소 힙을 사용하여 접근하였다.

주어진 scoville을 최소 힙에 대입하고 힙의 최상단에 위치한 원소의 값이 주어진 K값 이상일 때 까지 반복적으로 주어진 연산을 수행한다.

이 때, 반복적으로 연산을 수행하다가 힙의 마지막으로 남은 1개의 원소마저 K보다 작은 경우 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우로 판단하여 -1 을 return 하였다.

다른 사람의 풀이

( 문제를 맞춘 후 다른 사람의 풀이 보기를 참고)

풀이 방식은 나와 다를 것이 없었다.
우선순위 큐를 사용하였고 최소 힙의 특성을 이용해서 푼 풀이였다.

하지만 주어진 scoville 배열을 탐색하며 최소힙에 일일이 push 하지 않고 우선순위 큐를 선언함과 동시에 힙을 완성시키는 방법을 새롭게 알 수 있었다!

priority_queue<int, vector<int>, greater<int>> pq (scoville.begin(), scoville.end());

내 코드보다는 보다 간결하고, 가독성 있는 코드로 작성되어 있는 코드 같다!