[Programmers] 더 맵게

[Programmers] 더 맵게

 

🎈문제

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

💬설명

• 처음에는 PriorityQueue로 풀었는데 시간초과가 나서 heapq를 이용해 풀었다. 둘다 push pop이 O(logn)인걸로 알고 있는데 의문이었다.
• 찾아보니까 PriorityQueue는 heapq의 함수들을 이용해서 만들어졌지만 thread-safe한 대신 속도가 느리다고 한다. (참고)
• heapq로 우선순위 고려해서 풀어준다.

👩‍💻코드

# 시간 초과 코드


from queue import PriorityQueue


def solution(scoville, K):
    answer = 0
    pq = PriorityQueue()
    
    # priority queue에 모든 스코빌 지수 넣기
    for i in scoville:
        pq.put(i)
        
    # 스코빌 지수가 가장 작은 값이 K이상이 될때까지 반복
    while True:
        first = pq.get()
        if first >= K or not pq:
            return answer
        second = pq.get()
        # 가장 작은 값 둘다 0인경우 불가능
        if first == 0 and second == 0:
            return -1
        pq.put(first + second * 2)
        answer += 1
    
    return -1

# 정답코드


import heapq


def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
        
    # 스코빌 지수가 가장 작은 값이 K이상이 될때까지 반복
    while scoville[0] < K:
        first = heapq.heappop(scoville)
        second = heapq.heappop(scoville)
        heapq.heappush(scoville, first + second * 2)
        answer += 1
        if len(scoville) == 1 and scoville[0] < K:
            return -1
    
    return answer