14. 더 맵게

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

코딩테스트 연습 - 더 맵게

파이썬

def solution(scoville, K):
    from heapq import heappop, heapify, heappush
    heapify(scoville)
    answer = 0
    while len(scoville) > 1 and scoville[0] < K:
        heappush(scoville, heappop(scoville) + heappop(scoville) * 2)
        answer += 1
    return -1 if (scoville[0] < K) else answer
'''
테스트 1 〉	통과 (178.47ms, 118MB)
테스트 2 〉	통과 (409.91ms, 215MB)
테스트 3 〉	통과 (1916.74ms, 707MB)
테스트 4 〉	통과 (135.43ms, 95.9MB)
테스트 5 〉	통과 (2197.61ms, 740MB)
'''

파이썬은 임포트문을 함수내에서도 쓸 수 있습니다. 
파이썬의 heapq 모듈을 사용했습니다.
제 블로그에서도 소개한 적 있죠.
https://comdoc.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%9D%98-heapq-%EB%AA%A8%EB%93%88

자바

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> scoQ = new PriorityQueue<>();
        for (int each : scoville) {
            scoQ.add(each);
        }
        int answer = 0;
        while (scoQ.size() > 1 && scoQ.peek() < K) {
            scoQ.add(scoQ.poll() + scoQ.poll() * 2);
            answer++;
        }
        return (scoQ.peek() < K) ? -1 : answer;
    }
}
/*
테스트 1 〉	통과 (169.09ms, 70.3MB)
테스트 2 〉	통과 (270.52ms, 81.8MB)
테스트 3 〉	통과 (1152.23ms, 137MB)
테스트 4 〉	통과 (120.58ms, 68.3MB)
테스트 5 〉	통과 (1387.60ms, 141MB)
*/

인라인으로 변환하기 위해 스트림까지 동원했으나.. 깔끔하지 않아서.. 

import java.util.PriorityQueue;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> scoQ = new PriorityQueue<>(
                IntStream.of(scoville).boxed().collect(Collectors.toList())
        );
        int answer = 0;
        while (scoQ.size() > 1 && scoQ.peek() < K) {
            scoQ.add(scoQ.poll() + scoQ.poll() * 2);
            answer++;
        }
        return (scoQ.peek() < K) ? -1 : answer;
    }
}
/*
테스트 1 〉	통과 (162.77ms, 71.6MB)
테스트 2 〉	통과 (274.72ms, 86.8MB)
테스트 3 〉	통과 (1394.17ms, 145MB)
테스트 4 〉	통과 (142.63ms, 67.2MB)
테스트 5 〉	통과 (1415.91ms, 149MB)
*/