더 맵게

• 그냥 시키는 대로 구현하면 되고, 그 때 쉽게 떠오르는 방법은 우선순위 큐 (Priority Queue)를 쓰는 것. 코딩테스트 고득점 Kit에서도 우선순위큐의 연습문제로 분류되어있다.
  • 최솟값 우선순위 큐에 값들을 다 넣어놓고, 최솟값 두개를 pop 하고, 그것을 섞어서 만든 새 값을 push 하는 것을 반복하면 된다. pop과 push는 모두 O(logn)이고, 이것을 최대 n번 하므로 시간복잡도는 O(nlogn)
• 조금 생각해보면, 기존값들을 섞어서 만들어지는 값은 증가하는 순서로 만들어진다 (재료로 사용하는 값이 커지므로, 재료1+2*재료2 로 만들어지는 새 값도 커진다). 따라서 새로 만들어진 값들은 일반 큐에 저장하고, 추가할때는 맨 뒤에 push하는 것으로도 정렬된 순서를 유지할 수 있다.
• 그러면, 먼저 처음 주어진 원래 값들은 정렬해두고, 새 값을 저장할 큐를 만들어둔다. 최솟값을 뽑을때는 처음 주어진 값들중의 최솟값과 새 값들의 최솟값을 비교해서 작은 쪽을 빼내면 되고 이것은 O(1)이다. 최솟값 두개를 섞어서 새 값을 만들고 이것은 새값을 저장하는 큐의 뒤에 push 하는 것도 O(1).
• pop과 push가 모두 O(1)이므로, n번 처리하는데에는 O(n)이 걸린다. 다만 맨 처음에 원래 값들을 한번 정렬하는 시간이 O(nlogn)이므로, 전체 시간복잡도는 우선순위큐를 쓰는 방법과 같다. 하지만 실제 실행시간은 훨씬 더 단축된다.

"""Solution code for "Programmers 42626. 더 맵게".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42626
- Solution link: http://www.teferi.net/ps/problems/programmers/42626
"""

import heapq


def solution(scoville, K):
    heapq.heapify(scoville)
    for i in range(len(scoville) - 1):
        min_scov = heapq.heappop(scoville)
        if min_scov >= K:
            return i
        new_scov = min_scov + scoville[0] * 2
        heapq.heapreplace(scoville, new_scov)
    return i + 1 if scoville[0] >= K else -1

"""Solution code for "Programmers 42626. 더 맵게".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42626
- Solution link: http://www.teferi.net/ps/problems/programmers/42626
"""

import collections

INF = float('inf')


def solution(scoville, K):
    def pop_min():
        min_orig = orig_scovilles[-1] if orig_scovilles else INF
        min_new = new_scovilles[0] if new_scovilles else INF
        if min_orig < min_new:
            return orig_scovilles.pop()
        else:
            return new_scovilles.popleft()

    orig_scovilles = sorted(scoville, reverse=True)
    new_scovilles = collections.deque()

    for i in range(len(scoville) - 1):
        min_scov = pop_min()
        if min_scov >= K:
            return i
        second_min_scov = pop_min()
        new_scov = min_scov + second_min_scov * 2
        new_scovilles.append(new_scov)
    return i + 1 if new_scovilles[0] >= K else -1