[프로그래머스 python]더 맵게
2020-04-12https://programmers.co.kr/learn/courses/30/lessons/42626
| scoville | K | return |
|---|---|---|
| [1, 2, 3, 9, 10, 12] | 7 | 2 |
리스트를 우선순위 큐에 넣고 가장 작은거 두개를 빼서 처리하면 되겠다 싶었다.
모든 음식을 섞었는데도 원하는 매운맛에 도달하지 못하거나 이미 모두 충분히 매운맛이면 -1을 return 한다.
로직자체가 많이 어려워보이진 않아서 queue.PriorityQueue() 를 이용하여 금방 짰는데 줄줄히 시간초과로 터져나간다.
?? 우선순위큐를 쓰래서 우선순위큐를 썼는데 시간초과가 난다? 뭔가 이상하다싶어 루프를 줄여아하나 삽질을 시작했다.
원인은 PriorityQueue가 아니라 heapq를 사용해야 하는것이었다.
What's the difference between heapq and PriorityQueue in python?
PriorityQueue는 thread safe하고 heapq는 그렇지 못하다고한다. thread safe하면 아닌것에비해 속도가 느릴수밖에..
PriorityQueue를 이용했던 부분을 heapq로 수정하고나니 클리어할수있었다.
순한맛일줄알았는데 의외의 매운맛이었다.
"""
https://programmers.co.kr/learn/courses/30/lessons/42626
Programmers 42626 더 맵게
"""
# import queue
import heapq
def solution(scoville, K):
# pq = queue.PriorityQueue()
heapq.heapify(scoville)
count = 0
while len(scoville) > 0:
a = heapq.heappop(scoville)
if a >= K:
if count == 0:
return -1
else:
return count
if len(scoville) == 0:
break
b = heapq.heappop(scoville) * 2
heapq.heappush(scoville, a + b)
count += 1
return -1
# result == 2
s, k = [1, 2, 3, 9, 10, 12], 7
# result == -1
# s, k = [1, 1, 1, 1, 1, 1], 100
# result == 2
# s, k = [1,2,3], 11
print(solution(s, k))