[HackerRank] Jesse and Cookies

1주차 자료구조 복습
Practice > Data Structures > Heap

풀이

문제를 살펴보면 배열의 최소값이 주어진 K보다 커야 한다. 이때 최소힙으로 배열을 저장하면 top값이 k보다 크다면 아래 데이터는 무조건 k보다 큰 값을 가지게 된는 것을 알 수 있다. 

최소힙 구조

따라서 c++ STL에 구현되어 있는 priority_queue를 사용하여 최소힙으로 데이터를 저장하였다.

// priority_queue는 최대힙으로 구현되어 있기 때문에
//compare인자로 greater를 넘겨주어 최소힙으로 사용할 수 있다.
priority_queue<int, vector<int>, greater<int>> pq;

top 값을 최소로 만들어 주었으니 이 값이 만약 k보다 작으면서 priority_queue의 size가 1이라면 sweetness를 더 이상 올릴 수 없으므로 while문을 탈출하고 '-1'를 return하였다.

top 값이 k보다 작긴 하지만 아직 sweetness를 조합할 수 있다면(size >= 2), 조합하는 횟수(cnt)를 증가시키고 sweetness를 조합한 데이터를 다시 priority_queue에 넣어 주었다.

top 값이 k보다 크거나 같으면 조합 횟수를 return 한다.

전체적인 코드는 다음과 같다.

int cookies(int k, vector<int> A) {
    int cnt = 0, temp1, temp2;
    priority_queue<int, vector<int>, greater<int>> pq;
    
    for(int i=0; i<A.size(); i++)
        pq.push(A[i]);
        
    while(true){
        if(pq.top() < k){
            if(pq.size() == 1) break;
            cnt++;
            temp1 = pq.top(); pq.pop();
            temp2 = pq.top(); pq.pop();
            pq.push(temp1+temp2*2);
        }
        else return cnt;
    }
    return -1;
}

모든 예시를 맞춘 모습을 볼 수 있다.