[파이썬] 프로그래머스 힙(heap) - 더 맵게

10월 2주차 #3

 

문제 설명

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

 

효율성 통과한 풀이

효율성 통과 못한 풀이

처음엔 아래 방법으로 작성을 했다가 답은 맞아도 효율성은 하나도 통과를 못해서 질문을 보며 heap을 사용했다. 사실 주제부터가 heap이라 heap을 써야할 거 같긴했는데 heap 라이브러리를 잘 몰라서 일단 그냥 작성해보았다. 밑에 것도 답은 맞다. 문제 자체가 어렵다기보단 효율성을 따져서 작성하는게 어려웠던 문제인 것 같다. 처음 heap으로 작성했을 때에도 효율성을 통과 못해서 왜그런지 찾아봤는데 바보 같이 heapify를 안 해줬었다. 리스트를 heap처럼 사용하기 전에 heapify로 정렬을 해주고 사용해야한다..! 바보바보~~~ 반복문 끝내는 부분과 -1을 반환해야하는 경우도 생각해서 조건을 추가해주었다.