[프로그래머스] 더 맵게 문제풀이 python

🐒 문제

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

✍ 나의 풀이 (리팩토링 전)

import heapq

def solution(scoville, K):
    answer = 0
    
    if all(0==i for i in scoville):
        return -1

    hq = []
    for i in scoville:
        heapq.heappush(hq,i)

    while any(K>num for num in hq):

        least1 = heapq.heappop(hq)
        if hq:
            least2 = heapq.heappop(hq)
        else:
            return -1
        
        heapq.heappush(hq, least1 + (least2 * 2))
        answer += 1

    return answer

힙 카테고리에 있는 문제를 풀었다.

---

🧠 문제 이해

우선순위 큐를 이용해 문제를 풀었다.

파이썬에서는 heapq 라이브러리를 통해 우선순위 큐를 구현할 수 있다.

관련 블로그 https://littlefoxdiary.tistory.com/3

힙큐에서 pop 명령을 내리면 가장 작은 요소를 뱉어낸다.

pop을 한번 더하면 두번째로 작은 요소를 뱉어낸다.

이를 이용해 코드를 짰다.

---

⌨️ 리팩토링

if all(0==i for i in scoville):
        return -1

빠른동작을 위해 위 코드로 scoville이 모두 0인 경우에 -1 을 반환하게 했으나 처리시간이 증가했다. 그래서 삭제

    hq = []
    for i in scoville:
        heapq.heappush(hq,i)
   	
    #scoville의 요소를 하나씩 hq 힙에 넣는 코드
    
    
    대신
    
    heapq.heapify(scoville)
    
    #scoville 리스트를 힙큐로 바꿔주는 heapify사용

위 두가지를 수정하여

import heapq

def solution1(scoville, K):
    answer = 0
    
    heapq.heapify(scoville)

    while any(K>num for num in scoville):

        least1 = heapq.heappop(scoville)
        if scoville:
            least2 = heapq.heappop(scoville)
        else:
            return -1
        
        heapq.heappush(scoville, least1 + (least2 * 2))
        answer += 1

    return answer