[Python] 더 맵게

[코딩테스트 고득점 KIT - 힙]

 

 

힙큐(Heap Queue)와 우선순위 큐(Priority Queue)가 유사하다고 생각하여,

우선순위 큐를 사용하여 문제를 푸니 효율성 테스트에서 걸려 통과되지 않았다.

 

힙큐로 구현한 사람들이 많다하여,

왜 우선순위 큐로 하면 안되는건지 서칭을 하다...

https://slowsure.tistory.com/130 

 

아주 꼼꼼하게 써주신 글 덕분에

힙큐가 우선순위 큐보다 매우 빠르다는 것! - (PriorityQueue 는 Thread-Safe 하고 heapq는 Non-safe, 확인절차에서 시간)

 

문제는 힙큐에서 작은 순으로 빠져나오는 값을

리스트에 담아주며 K 값을 못넘는 경우 정해진 수식을 통하여 계산하고 다시 힙큐에 담는다.

 

이 과정을 반복하여

모든 값이 K 이상이 될 수 있는지 확인 후,

answer 값을 반환.

 

끝

 

import heapq as hq
 
def solution(scoville, K):
    answer = 0
 
	# heapq의 장점, heapify를 통한 리스트-> heapq 변환
    # 우선순위 큐는 for문을 통해 초기값을 대입해줘야한다.
    hq.heapify(scoville)
    h = []
    count = 0
 
    while scoville:
		
        # 가장 작은 값이 K 이상이라면, 모든 값이 K 이상일 것
        # h 리스트에 값이 존재한다면, 0 번째 값이 최소가 아닐 수 있다.
        if scoville[0] >= K and not h:
            return count
        h.append(hq.heappop(scoville))
		
        # K 이하 값 두개를 연산하여 새로운 스코빌 지수 생성
        if len(h) == 2:
            count += 1
            total = h[0] + h[1] * 2
 
            h = []
            hq.heappush(scoville, total)
 
 
    return -1