[Algorithm] 더 맵게 : 프로그래머스 - Heap

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

코딩테스트 연습 - 더 맵게

 

위 알고리즘은 힙을 이용한 트리검색을 통해

지정한 숫자보다 작은수가 없을 때 까지 연산을 진행하는 알고리즘 이다.

 

문제의 풀이는 자바에서 힙 구조로 이루어진 우선순위 큐 (Priority Queue) 를 이용하여 문제를 해결하였다.

 

import java.util.PriorityQueue;
class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
		
		PriorityQueue<Integer> queue = new PriorityQueue<>();
		for(int i:scoville) {
			queue.add(i);
		}
		
		while(true) {
			// 우선순위 큐는 힙 트리로 구성되어 있어 
			// 자료들이 항상 정렬되어 있다.
			// 큐의 peek을 이용하여 가장 앞단 (가장작은수) 을 체크하여 K보다 크거나 갔다면
			// 모든 숫자가 K 보다 크므로 반복문 종료.
			if(queue.peek()>=K) {
				break;
			// 큐에 데이터가 2개 이상 있을때만 진행.
			}else if(queue.size()>=2){
				int min = queue.poll();
				int second = queue.poll();
				int mix = min+(second*2);
				queue.add(mix);
				answer++;
			}else {
				// 해당 조건에 들어온 경우 : size가 1인데 해당값이 K보다 작은 경우.
				// 위 조건은 제한사항 중 모든 음식의 스코빌 지수를 K 이상으로 
				// 만들 수 없는 경우이므로 -1을 출력시킴과 동시에 반복문을 종료한다.
				answer = -1;
				break;
			}
		}
		return answer;
    }
}