프로그래머스 더 맵게 자바 풀이

문제 링크

문제 요약

스코빌 지수가 가장 낮은 두 음식을 골라 가장 낮은 값 + 두 번째로 낮은 값 * 2 로 섞는다
모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복한다
모든 음식을 K 이상으로 만들 수 없으면 -1을 반환한다

문제 풀이

처음에는 매번 배열을 정렬해서 가장 작은 두 값을 찾아 섞고, 다시 배열에 넣는 방식을 생각했다.

하지만 이 방식은 비효율적이다.

scoville의 길이가 최대 1,000,000이고, 섞는 연산은 최악의 경우 배열 크기만큼 반복될 수 있다.

매번 정렬하면 반복마다 O(n log n)이 들어서 전체로는 감당이 안 된다.

이 문제의 핵심은 가장 작은 두 값만 빠르게 꺼내고 다시 넣을 수 있으면 된다는 점이다.

전체를 다시 정렬할 필요 없이, 최소 힙(PriorityQueue)에 모든 값을 넣어두면 된다.

힙에서 가장 작은 값을 꺼낸다. 이 값이 이미 K 이상이면 반복을 끝낸다.
힙이 비어 있으면 더 섞을 음식이 없다는 뜻이므로 -1을 반환한다.
아니면 두 번째로 작은 값을 마저 꺼내 섞은 값을 계산해서 다시 힙에 넣는다.

이렇게 하면 한 번의 섞기 연산이 O(log n)으로 끝난다.

섞은 값이 int 범위를 넘어갈 수 있어서 힙과 계산은 long으로 처리했다.

최종 코드

java

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        PriorityQueue<Long> pq = new PriorityQueue<>(); // 최소 힙: 가장 작은 스코빌 지수가 항상 앞에 온다
        for(int s : scoville){ // 모든 음식을 힙에 넣는다
            pq.add((long)s);
        }
        
        while(!pq.isEmpty()){
            long a = pq.poll(); // 가장 작은 값
            if(a >= K) // 이미 K 이상이면 더 섞을 필요 없음
                break;
            if(pq.isEmpty()) // 섞을 음식이 하나도 안 남았으면 불가능
                return -1;
            
            long b = pq.poll(); // 두 번째로 작은 값
            
            pq.add(a+b*2); // 섞은 음식을 다시 힙에 넣는다
            
            answer++;
        }
        return answer;
    }
}

더 맵게

문제 요약

문제 풀이

최종 코드

함께 읽으면 좋은 글

택배상자

롤케이크 자르기

할인 행사

숫자 변환하기