[프로그래머스/파이썬] 더 맵게 풀이 (Python, heap, heapq, heapify, heappush, heappop, 최소힙)

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

(Python, heap, heapq, heapify, heappush, heappop, 최소힙)

 

1. 문제

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

프로그래머스

 

 

2. 코드

import heapq

def solution(scoville, K): #스코빌 리스트, 기준 스코빌 K
    heapq.heapify(scoville) # 스코빌 리스트
    
    answer = 0
    while len(scoville) >=2: # 항상 2개보다 많아야 비교 가능 (완전이진트리)

        # 1. heappop2번하기 
        firstScoville = heapq.heappop(scoville)
        
        # 2.1. 만약 heapop 했을때 K보다 크면 실행종료 return
        if firstScoville >= K:
            return answer
        
        # 2.2. heappop 한번 더해서, 두번째 값 받아오기
        secondScoville = heapq.heappop(scoville)
        
        # 3. 받아온 두 값을 (1값 * 2*2) 해서 heappush하기 
        mixScoville = firstScoville + (secondScoville*2)
        
        heapq.heappush(scoville, mixScoville)
        
        # 4. count +=1하기 
        answer+=1
    
    #5. 만약 다 섞었는데도 부족하고 len 1이라면 -1 return
    if scoville[0] < K:
        return -1
    
    return answer

 

 

3. 풀이

1. 입력받은 스코빌 리스트를 heap 자료구조로 만들어줍니다. 

- 파이썬에서는 heapq (우선순위 큐) 라이브러리가 있습니다. 

- heapq.heapify()를 이용하여 리스트를 heap으로 변경합니다. 

heapq.heapify(scoville) # 스코빌 리스트

 

 

2. 두개의 음식을 항상 뽑아야 하기 때문에, scoville 힙의 개수가 2 이상일 때까지 반복합니다. 

while len(scoville) >=2: # 항상 2개보다 많아야 비교 가능 (완전이진트리)

 

 

3. 최솟값을 두번 꺼내기 위해, heappop을 2번 해줍니다. 이때, 만약 현재 꺼낸 값이 기준 스코빌지수(K) 보다 크면, 더 이상 실행을 하지 않아도 되기 때문에 횟수(answer)를 반환합니다. 

 # 1. heappop2번하기 
        firstScoville = heapq.heappop(scoville)
        
        # 2.1. 만약 heapop 했을때 K보다 크면 실행종료 return
        if firstScoville >= K:
            return answer
        
        # 2.2. heappop 한번 더해서, 두번째 값 받아오기
        secondScoville = heapq.heappop(scoville)

-heap.heappop(heap) : 힙에서 최솟값을 꺼냅니다.

 

 

4. 3번에서 꺼낸 두개의 스코빌 지수를 문제에 나온 대로 계산해서, heap에 추가해 줍니다.  

# 3. 받아온 두 값을 (1값 * 2*2) 해서 heappush하기 
        mixScoville = firstScoville + (secondScoville*2)
        
        heapq.heappush(scoville, mixScoville)

- heapq.heappush(heap, 추가 값) : 힙에 item을 추가합니다. 

 

5. 반복문에서 비교 및 추가 로직이 끝났다면, 횟수를 1 증가시킵니다. 

        # 4. count +=1하기 
        answer+=1

 

 

6. 만약, 모든 음식들의 스코빌 지수를 섞어서 반복문을 탈출 했음에도 아직 return이 되지 않았다면, 마지막 남은 수가 기준 K를 넘는지 확인해야 합니다. 

    if scoville[0] < K:
        return -1

- scoville[0]번의 값이 기준 K보다 작다면, -1을 반환합니다.

 

 

7. 마지막 결과를 return 합니다. 

return answer

---

4. 마무리

힙을 몰랐다면, 그냥 max(), min() 함수를 이용한 방법이나 정렬을 한 다음에 값을 꺼내는 등의 비효율 적인 방법으로 구현을 했을 것 같습니다. 힙 자료구조는 안쓰면 늘 까먹기 때문에 계속 반복해서 학습해야 할 것 같네요! 

 

 

- 참고 풀이 

https://littlefoxdiary.tistory.com/3

[Python] 힙 자료구조 / 힙큐(heapq) / 파이썬에서 heapq 모듈 사용하기