[프로그래머스 알고리즘] 프로그래머스 Lv.2: 더 맵게 / 파이썬 Python3 (힙(Heap))
🔔 문제
출처 : https://programmers.co.kr/learn/courses/30/lessons/42626
문제 설명
매운 것을 좋아하는 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 합니다.
입출력 예
| scoville | K | return |
|---|---|---|
| [1, 2, 3, 9, 10, 12] | 7 | 2 |
입출력 예 설명
- 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다. 새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5 가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]
- 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다. 새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13 가진 음식의 스코빌 지수 = [13, 9, 10, 12]
모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.
📝 들어가기 전에…
자료구조인 ‘힙(Heap)’ 에 대해 잘 몰라 공부하기 위해 이 문제를 풀었다.
힙을 공부하기 위한 것이었으므로 당연히 힙에 대해서 어느정도 찾아서 학습한 다음에 그것을 토대로 이 문제를 풀었다.
(역시… 찾아보니 힙을 쓰지 않고, 다른걸로 구현해서 테스트케이스나 효율성 검사에서 통과가 안된 사람도 다소 있었다. 주제가 제시 되어있다면, 주제에 맞는 자료구조나 알고리즘 방식을 써야 역시 효율적으로 잘 풀린다.)파이썬에는
heapq모듈을 import해서 쓸 수 있기 때문에 다른 언어에 비해 비교적 되게 편하게 풀 수 있는 것 같다.
(갓 파이썬!)
🔐 해결 (소스 코드)
import heapq
def solution(scoville, K):
result = 0
heapq.heapify(scoville)
while scoville[0] < K:
# 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
mix = heapq.heappop(scoville) + (heapq.heappop(scoville) * 2) # heappop은 heap 안에서 가장 적은 요소를 pop해줌
heapq.heappush(scoville, mix)
result += 1
# 제한 사항 : 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return
if len(scoville) == 1 and scoville[0] < K:
return -1
return result
😓 후기
역시, 코딩테스트(알고리즘) 문제는 아무리 어려워 보이거나 모르는 부분의 문제라도 공부한다고 생각하고, 하나하나씩 이해하면 새롭게 알아가는 재미가 있는 것 같다.
이 문제 덕분에 힙(Heap)이라는 자료구조에 대해서 새롭게 알게 되었지만, 잘 알게 되었다.
그러나, 아직 알아야되고, 해결할 줄 알아야하는 알고리즘, 자료구조 그리고 문제유형들이 많이 남아있다.
화이팅!!! 💪
Leave a comment