[프로그래머스] 파이썬 _ 더 맵게

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

코딩테스트 연습 - 더 맵게

 

문제유형 : 힙

 

문제풀이 :

• 여러개의 값중에서 최대값이나 최솟값을 빠르게 찾도록 고안된 자료구조인로 힙을 사용한다.
• 이 문제도 여러개의 값 중에서 가장 작은값을 차례로 2개씩 빼내서 비교하여 넣는 것이므로 우선적으로 가장 작은값을 뽑아내는것이 필요하다.  이때 단순히 min내장함수를 통해 리스트의 최솟값을 찾으면 O(n)시간이 걸리므로 시간초과가 날것이다.
• 한번의 반복마다
  • 1. 힙에서 차례로 2개씩 빼서 새로운 음식을 만들어 힙에 추가한다.
  • 2. 최소힙에서 값을하나 뺀것이 이미 스코빌지수를 넘었다면끝낸다.
  • 3. 힙에 남은 값이 1개인데, 이 1개가 스코빌지수보다 낮다면 -1을 리턴한다.

 

• 최댓값이나 최솟값을 찾는것이 반복적으로 필요한 문제에서는 힙 자료구조를 꼭 기억하자! 🎅🏻

 

기억해야할 내장함수

• heapify() - 리스트를 한번에 힙으로 바꿔주는 함수
• 팝 하지 않고 가장 작은 항목에 액세스하려면, heap[0]을 사용한다.

 

정답코드 :

# 힙 자료구조를 사용한다.
# 한번의 반복마다 
# 1. 힙에서 차례로 2개씩 빼서 새로운 음식을 만들어 힙에 추가한다.
# 2. 최소힙에서 값을하나 뺀것이 이미 스코빌지수를 넘었다면끝낸다.
# 3. 힙에 남은 값이 1개인데, 이 1개가 스코빌지수보다 낮다면 -1을 리턴한다.
import heapq


def solution(s, K):
    heapq.heapify(s)

    depth = 0
    while len(s) > 1:
        depth +=1
        a = heapq.heappop(s)
        b = heapq.heappop(s)

        new = a + (b*2)
        heapq.heappush(s, new)
        
        min_value = s[0] #팝 하지 않고 가장 작은 항목에 액세스하려면, heap[0]을 사용하십시오.
        if min_value > K:
            return depth
    return -1