[프로그래머스] 더 맵게

1. 문제

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

2. 풀이

2.1. PriorityQueue를 이용한 시간초과 풀이

PriorityQueue 를 사용하여 문제를 해결한 풀이입니다.
문제 해결 방법은 아래와 같습니다.
- PriorityQueue 에 남은 원소가 2개 이상일 경우에 계속해서 로직을 수행합니다.
  - 가장 적은 2개를 뽑아서 2개 다 0이 아닌지 확인하고, 다음 값을 PriorityQueue에 집어 넣습니다.
- while 문이 끝나고 나서 PriorityQueue 에 들어있는 요소를 확인하고, K 보다 적으면 -1를 return 합니다.
로직에는 이상이 없지만 PriorityQueue를 사용한 사람들은 전부 시간 초과가 난 것 같습니다. 찬우의 이것저것블로그를 참조하면서 힌트를 얻을 수 있었습니다.
- 이유는 PriorityQueue는 thread safe & heapq는 not thread safe 이기 때문이라고 합니다. 위키피디아에서는 thread safe를 아래와 같이 언급하고 있습니다.
  
  thread safe란 번역하면 스레드 안전으로 멀티 스레드 프로그래밍에서 일반적으로 어떤 함수나 변수, 혹은 객체가 여러 스레드로부터 동시에 접근이 이루어져도 프로그램의 실행에 문제가 없음을 뜻한다. 보다 엄밀하게는 하나의 함수가 한 스레드로부터 호출되어 실행 중일 때, 다른 스레드가 그 함수를 호출하여 동시에 함께 실행되더라도 각 스레드에서의 함수의 수행 결과가 올바로 나오는 것으로 정의한다.
- Queue는 고려하는 것이 많기 때문에 속도가 더 느리고, heapq 를 사용하는 것이 더 낫다고 합니다.
  
  The Queue module implements multi-producer, multi-consumer queues. It is especially useful in threaded programming when information must be exchanged safely between multiple threads. The Queue class in this module implements all the required locking semantics. It depends on the availability of thread support in Python; see the threading module. This makes the heapq module faster; there is no locking overhead. In addition, you are free to use the various heapq functions in different, novel ways, the PriorityQueue only offers the straight-up queueing functionality.

from queue import PriorityQueue
def solution(scoville, K):
    shake = 0
    pq = PriorityQueue()
    for x in scoville:
        pq.put(x)

    while True:
        if pq.qsize() < 2:
            break
        min_0, min_1 = pq.get(), pq.get()
        if min_0 >= K or min_1 == 0:
            pq.put(min_0)
            pq.put(min_1)
            break
        pq.put(min_0 + 2 * min_1)
        shake += 1

    if pq.get() < K:
        return -1

    return shake

2.2. heap을 이용한 풀이

위의 PriorityQueue를 heapq로 변경하여 풀면 됩니다.

import heapq
def solution(scoville, K):
    shake = 0
    pq_heap = []

    for i in scoville:
        heapq.heappush(pq_heap, i)

    while pq_heap[0] < K:
        if len(pq_heap) == 1 and pq_heap[0] < K:
            return -1

        heapq.heappush(pq_heap, heapq.heappop(pq_heap) + heapq.heappop(pq_heap) * 2)
        shake += 1
    return shake

reference

https://blog.chanwookim.me/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-python-%EB%8D%94-%EB%A7%B5%EA%B2%8C.html
https://ko.wikipedia.org/wiki/%EC%8A%A4%EB%A0%88%EB%93%9C_%EC%95%88%EC%A0%84
https://stackoverrun.com/ko/q/10198220

PREVIOUS[프로그래머스] 프린터 풀이

NEXTWhat is mkdir -p option on linux?