[프로그래머스/42626/level2/고득점kit] 더 맵게 - Heap 정렬 / 우선순위 큐 / 최소 힙

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42626

• 어떻게 풀었는가?
  • 우선순위대로 계속 정렬해야하는 문제니까 => 힙 정렬 사용하자
    • 스코빌 지수 기준 최소 힙 생성 -> 가장 작은 값 2개 pop -> 섞은 음식으로 가공 후 push-
    • 모든 음식이 k이상이 될때까지 반복 = 루트 노드가 K이상이 될때까지 진행

 

1차 풀이 - 효율성 통과 / 정확성 실패(문제 잘 안읽음)

• 에러 이유 → 조건 2개 안읽음
  • 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.
  • 2개씩만 묶을 수 있으니 루프는 원소가 2개남았을때까지가 마지노선이다

'''
우선순위대로 계속 정렬해야하는 문제니까 => 힙 정렬 사용하자
- 스코빌 지수 기준 최소 힙 생성 -> 가장 작은 값 2개 pop -> 섞은 음식으로 가공 후 push
- 모든 음식이 k이상이 될때까지 반복 = 루트 노드가 K이상이 될때까지

'''
import heapq

def solution(scoville, K):
    answer = 0
    
    # 최소 힙 생성
    h = []
    for s in scoville:
        heapq.heappush(h, s) 
    
    while h:
        m = heapq.heappop(h)
        if m >= K: #루트 노드가 K이상이 될 때까지
            break
        
        heapq.heappush(h, m + heapq.heappop(h) * 2)
        answer += 1
    
    return answer

2차 풀이 - 통과

'''
우선순위대로 계속 정렬해야하는 문제니까 => 힙 정렬 사용하자
- 스코빌 지수 기준 최소 힙 생성 -> 가장 작은 값 2개 pop -> 섞은 음식으로 가공 후 push
- 모든 음식이 k이상이 될때까지 반복 = 루트 노드가 K이상이 될때까지

'''
import heapq

def solution(scoville, K):
    answer = 0
    
    # 최소 힙 생성
    h = []
    for s in scoville:
        heapq.heappush(h, s) 
    
    while len(h) > 1:
        m = heapq.heappop(h)
        if m >= K: #루트 노드가 K이상이 될 때까지
            break
        
        heapq.heappush(h, m + heapq.heappop(h) * 2)
        answer += 1
    
    # 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우
    if heapq.heappop(h) < K:
        return -1
    
    return answer