[자료구조] [heapq] Jesse and Cookies

다음의 문제는 heapq을 활용해서 푸는 문제에 해당한다.  

Hackerrank의 Data structures 관한 문제 중에서 Easy에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. 

www.hackerrank.com/challenges/jesse-and-cookies/problem

Jesse and Cookies | HackerRank

 

 

• "전체 쿠키의 당도 정보가 포함되어 있는 리스트중에서, 전체 쿠키가 만족시켜야 하는 최소한의 당도가 있다." 문제 설명을 읽으면서, 힙 모듈을 사용해야 겠다는 아이디어를 생각한 부분이다. 쿠키 당도 리스트를 힙 자료형으로 만든 후(heapify), 연산을 통해서 새로운 쿠키를 힙에 추가(heappush)하면서 총 연산의 횟수를 구한다.

 

import os
import sys
import heapq as H

#
# Complete the cookies function below.
#
def cookies(k, A):
    #k = 모든 쿠키가 만족시켜야 하는 최소한의 당도
    #A = 쿠키의 당도 정보가 포함되어 있는 리스트
    # Write your code here.
    
    H.heapify(A)
    answer = 0 
    while True:
        if len(A) == 1 and A[0]<k:
            return -1
        
        if A[0] >= k:
            return answer
        else:
            least1 = H.heappop(A)
            least2 = H.heappop(A)
            new_one = least1 + 2*least2
            answer +=1
            H.heappush(A, new_one)