[프로그래머스 - Level 2] 더 맵게(파이썬, heapq)

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

코딩테스트 연습 - 더 맵게

 

<복습 체크>

22/02/13
O

 

<내 코드>

- scoville을 heap으로 만들기 위해 heapify를 이용해서 작은순서로 정렬했다.

- while문은 길이가 2 이상인경우에만 실행(2보다 작을 때 pop을 할때 오류가 난다.)

- 이 때, 스코빌의 가장 작은 값이 K 이상이 되면 break한다.

- 가장 작은 값, 두번 째 작은값을 차례로 heappop을 통해 힙에서 빼낸다.

- 그리고 heappush를 이용해서 섞은 음식의 스코빌 지수를 다시 넣어준다. (heap은 알아서 정렬됨)

- 그리고 answer을 증가시켜서 섞은 횟수를 증가시킨다.

- while문 종료후에 scoville의 가장 작은 원소가 K미만이면 모든 음식을 스코빌 지수 이상으로 만들 수 없는 경우이므로

  -1을 리턴한다.

import heapq
def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    while len(scoville)>=2:
        #가장 앞에 있는 원소(작은 원소)가 K이상이면 종료
        if scoville[0] >=K: 
            break
            
        temp1 = heapq.heappop(scoville)
        temp2 = heapq.heappop(scoville)
        heapq.heappush(scoville, temp1+temp2*2)
        answer+=1
        
    if scoville[0] <K:
        answer = -1
    return answer

 

 

 

- 파이썬의 heapq를 이용해서 구현하였다.

- heapq는 기본적으로 최소힙으로 구현되어있다. 즉, 루트 노드가 가장 작고, 모든 부모노드는 자식 노드보다 작다

import heapq

def solution(scoville, K):
    answer = 0
    #스코빌 리스트로 힙 만들기
    heapq.heapify(scoville)
    
    while len(scoville) >=2: #인덱스 에러 방지
        min_ = heapq.heappop(scoville)
        
        if min_>=K:
            break
            
        else:
            min2 = heapq.heappop(scoville)
            heapq.heappush(scoville,min_+(min2*2))
            answer+=1
            
    if scoville[0]<K:
        answer = -1
    
    
    return answer