[프로그래머스/java] 더 맵게 (PriorityQueue)

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

코딩테스트 연습 - 더 맵게

 

• 연산 후 계속해서 제일 작은 값 2개를 찾아 진행하므로 최소힙 이용
  • PriorityQueue

https://conanglog.tistory.com/222

[JAVA] 우선순위큐 PriorityQueue 사용하기

 

 

 

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        PriorityQueue<Integer> heap = new PriorityQueue<>(); // 최소힙
        
        for(int i = 0; i < scoville.length; i++) {
            heap.offer(scoville[i]); // 힙에 배열 값들 넣어주기
        }
        
        while(heap.peek() < K) { // root(제일 작은 값)가 k보다 작으면 실행 / 커지면 그만
            if(heap.size() < 2)
                return -1;
            
            int lowScov1 = heap.poll(); // 제일 작은 root 꺼내서 변수에 넣기
            int lowScov2 = heap.poll(); // 한번 꺼냈으니까 얘는 2번째로 작은 수가 됨
            
            int mixFood = lowScov1 + (lowScov2 * 2); // 문제에 있는 공식
            
            heap.offer(mixFood); // 더한 값을 다시 힙에 넣어주기
            answer++; // 섞는 횟수 증가
        }
        
        return answer;
    }
}