[코딩테스트] 더 맵게

문제

---

더 맵게 문제 바로가기

제출 코드(Java)

---

코드 제출

import java.util.*;

class Solution {
  public  int solution(int[] scoville, int k) {
        Queue<Integer> queue = initQueue(scoville);
        int result = 1;
   
        for (; result < scoville.length; result++) {
            mixScoville(queue);
            if (queue.peek() >= k ) {
                return result;
            }
        }

        return -1;
    }

    private int mixScoville(Queue<Integer> queue) {
        int minScoville = queue.poll();
        int secondMinScoville = queue.poll();
        int mixScoville = minScoville + (secondMinScoville * 2);
        queue.add(mixScoville);
        return mixScoville;
    }

    private Queue<Integer> initQueue(int[] scoville) {
        Queue<Integer> queue = new PriorityQueue<>();
        for (int i : scoville) {
            queue.add(i);
        }
        return queue;
    }
}

Java에서 지원해주는 우선순위 큐를 사용해 쉽게 풀어냈다.

정확성 테스트

정확성  테스트
테스트 1 〉	통과 (0.38ms, 52.2MB)
테스트 2 〉	통과 (0.40ms, 52.1MB)
테스트 3 〉	통과 (0.45ms, 52.5MB)
테스트 4 〉	통과 (0.42ms, 53.1MB)
테스트 5 〉	통과 (0.39ms, 52.3MB)
테스트 6 〉	통과 (3.84ms, 52.4MB)
테스트 7 〉	통과 (2.37ms, 53MB)
테스트 8 〉	통과 (0.94ms, 51.8MB)
테스트 9 〉	통과 (0.94ms, 52.9MB)
테스트 10 〉	통과 (4.45ms, 52.6MB)
테스트 11 〉	통과 (2.11ms, 52MB)
테스트 12 〉	통과 (3.72ms, 52.9MB)
테스트 13 〉	통과 (2.91ms, 51.9MB)
테스트 14 〉	통과 (0.51ms, 52.2MB)
테스트 15 〉	통과 (4.33ms, 53.6MB)
테스트 16 〉	통과 (0.40ms, 52.9MB)
효율성  테스트
테스트 1 〉	통과 (145.84ms, 66.7MB)
테스트 2 〉	통과 (253.70ms, 86.4MB)
테스트 3 〉	통과 (1423.07ms, 122MB)
테스트 4 〉	통과 (114.33ms, 64.1MB)
테스트 5 〉	통과 (1253.06ms, 123MB)

이제 다른 사용자들의 답변을 봐도 차이가 별로 없다.
숨은 고수들의 답변을 참조하고 싶은데 프로그래머스에 효율성 좋은 순의 정렬 필터가 있었으면,,,

제출 코드(Python)

---

코드 제출

import heapq

def mixScoville(minScoville, heap):
    minSecondScoville = heapq.heappop(heap)
    heapq.heappush(heap, (minScoville + (2 * minSecondScoville)))


def solution(s, k):
    answer = 1
    scovilleLen = len(s)
    heapq.heapify(s)
    minScoville = heapq.heappop(s)


    for i in range(0, scovilleLen - 1):
        mixScoville(minScoville, s)
        minScoville = heapq.heappop(s)
        if minScoville >= k:
            return answer
        answer += 1

    return -1

파이썬에서 제공해주는 heapq를 사용해 풀어낸 문제. thread-safe하진 않지만 속도가 빠른 heapq를 차용했다

정확성 테스트

정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.01ms, 10.3MB)
테스트 3 〉	통과 (0.01ms, 10.2MB)
테스트 4 〉	통과 (0.01ms, 10.2MB)
테스트 5 〉	통과 (0.01ms, 10.1MB)
테스트 6 〉	통과 (0.72ms, 10.2MB)
테스트 7 〉	통과 (0.61ms, 10.2MB)
테스트 8 〉	통과 (0.08ms, 10.2MB)
테스트 9 〉	통과 (0.07ms, 10.1MB)
테스트 10 〉	통과 (0.49ms, 10.2MB)
테스트 11 〉	통과 (0.30ms, 10.2MB)
테스트 12 〉	통과 (1.08ms, 10.2MB)
테스트 13 〉	통과 (0.77ms, 10.2MB)
테스트 14 〉	통과 (0.02ms, 10.2MB)
테스트 15 〉	통과 (0.78ms, 10.3MB)
테스트 16 〉	통과 (0.01ms, 10.2MB)
효율성  테스트
테스트 1 〉	통과 (182.79ms, 16.3MB)
테스트 2 〉	통과 (360.11ms, 22MB)
테스트 3 〉	통과 (1793.08ms, 49.9MB)
테스트 4 〉	통과 (133.45ms, 15MB)
테스트 5 〉	통과 (1667.71ms, 51.9MB)

파이썬에는 지원하지 않는 method들이 많지 않다는걸 새삼 깨달았다... peek()가 없다니 ㅜ
peek()가 없어 이전 최소값은 변수에 담아 재사용하는 방식으로 풀어냈다.