[Programmers / Level 2] 42626. 더 맵게 (Java)

💡 Info

• 난이도: Lv2
  프로그래머스 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42626
  풀이 링크(GitHub): hayannn/CodingTest_Java/프로그래머스/2/더 맵게

입출력 조건

입출력 예시

문제 이해

• 음식 스코빌 지수 배열과 스코빌 지수 변수가 주어졌을 때, 스코빌 지수를 K 이상으로 만들기 위해 섞는 최소 횟수를 구하는 문제

알고리즘

풀이 시간 : 분

• 최소 힙 생성 : 모든 음식의 스코빌 지수를 작은 순서대로 관리
• 반복 섞기
  • 가장 작은 두 값을 꺼내 새 스코빌 계산(첫번째 + 두번째*2)
  • 새로운 값 -> 힙에 추가, 횟수 증가
• 가장 작은 값이 K 이상이면 종료, 불가능한 경우 -1을 반환

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int s : scoville) {
            pq.add(s);
        }

        while (pq.size() > 1 && pq.peek() < K) {
            int first = pq.poll();
            int second = pq.poll();
            int newScoville = first + (second * 2);
            pq.add(newScoville);
            answer++;
        }
        
        if (pq.peek() < K) {
            return -1;
        }

        return answer;
    }
}

결과