[Python] 프로그래머스 - 더 맵게

1.문제정보

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

프로그래머스

 

2. 풀이

정렬된 데이터 큐에서 가장 작은 2개를 선택하여 값을 계산한 후 다시 데이터 큐에 값을 저장하는 것을 반복하면 된다. 문제는 계산을 반복하면서 데이터 목록을 계속 정렬해줘야 하는 부분이였다. 기존에 우선순위 큐(Priority Queue)에 대해서 알고 있어서 우선순위 큐로 문제 풀이를 시도하였다. 결과는 일부 케이스에서 시간초과를 받았다. 답을 만들 수 없는 경우(-1)에 대해서 수학적인 방법으로 구할 수 있나 고민해봤지만 답을 찾지 못했다.

 

구글링을 하던 중 heapq 모듈에 대해서 알게되었다. heapq에서도 힙 안의 데이터를 계속 하는 점이 우선순위 큐와 같았는데 차이를 보니 우선순위 큐는 Thread Safe, heapq 모듈은 Thread Safe하지 않았다. Thread Safe를 지원하는 쪽이 당연히 오래걸릴 것이기 때문에  heapq 모듈로 변경하였더니 문제를 해결할 수 있었다.

 

3. 소스코드

# from queue import PriorityQueue # thread safe
import heapq # none thread safe

def solution(scoville, K):
    q = []
    for scov in scoville:
        heapq.heappush(q, scov)

    answer = 0
    while q:
        min1 = heapq.heappop(q)
        # 최소 스코빌이 K이상이라 LOOP 탈출
        if min1 >= K:
            break
        
        # 큐에 더이상 혼합할 스코빌이 없을때, K이상의 스코빌을 만들 수 없다..
        if not q:
            answer = -1
            break
        min2 = heapq.heappop(q)

        # 스코빌 혼합 후 큐에 저장, 횟수 1증가
        mix = min1 + 2*min2
        heapq.heappush(q, mix)
        answer += 1
    return answer

 

4. 배운점

파이썬에서 우선순위 기능을 제공하는 큐는 Priority Queue와 heapq 모듈이 있다. 그 차이는 Priority Queue는 Thread Safe하고, heapq 모듈은 Thread Safe하지 않다는 점이다. 때문에 멀티 스레드 환경이 아니라면 heapq 모듈로 처리하는 것이 속도면에서 훨씬 유리하다.