99클럽 코테 스터디 9일차 TIL - [프로그래머스] 더 맵게 (Java)

📌 오늘의 학습 키워드

[프로그래머스] 더 맵게 (Java)
https://school.programmers.co.kr/learn/courses/30/lessons/42626

📌 공부한 내용 본인의 언어로 정리하기

문제 탐색하기

입력 : 음식의 스코빌 지수 배열 scoville, 원하는 스코빌 지수 K (2 ≤ scoville.length ≤ 1,000,000, 0 ≤ K ≤ 1,000,000,000)
출력 : 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수 (불가능하면 -1)

가능한 시간복잡도

O(nlogn)

알고리즘 선택

힙

📌 코드 설계하기

1.주어진 scoville 배열의 모든 요소를 힙에 추가한다.
2. 큐의 크기가 1보다 크고, 가장 작은 요소가 K보다 작은 경우에만 섞는 작업을 수행한다.
3. 가장 작은 두 요소를 poll()로 제거하고, 새로운 스코빌 지수를 계산해 큐에 다시 추가한다.
4. 섞는 횟수를 count에 기록한다.
5. 반복 작업이 끝난 후에도 가장 작은 요소가 K보다 작으면 모든 음식을 K 이상으로 만들 수 없으므로 -1을 반환하고, 그렇지 않으면 섞는 횟수를 반환한다.

📌 오늘의 회고

어떤 문제가 있었고, 나는 어떤 시도를 했는지

없음

어떻게 해결했는지

없음

무엇을 새롭게 알았는지

PriorityQueue는 최소 힙으로 구현된다.

내일 학습할 것은 무엇인지

구현

📌 정답 코드

import java.util.*;

public class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        
        for (int s : scoville) {
            heap.add(s);
        }
        
        int count = 0;
        
        while (heap.size() > 1 && heap.peek() < K) {
            int first = heap.poll();
            int second = heap.poll();
            int mixed = first + (second * 2);
            heap.add(mixed);
            count++;
        }
        
        if (heap.peek() < K) {
            return -1;
        }
        
        return count;
    }
}