[JAVA] Programmers <Heap_LV2> 더 맵게

계산식:

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

개인적으로 이렇게 테스트 케이스를 하나만 주는 경우를 굉장히 싫어한다. 테스트 케이스'만' 성공했을 때 그 반례를 찾기가 너무 시간이 오래걸려서 잘못하면 진짜 몇시간씩 진전도 없이 날리는 경우가 생기기 때문에.... 

이 문제는 어제 포스팅에서 정리한 Heap이나 Priority Queue만 잘 활용하면 별 문제 없이 해결할 수 있는 문제이다.

우선 받은 스코빌 지수 배열을 모두 Priority Queue에 저장하여 insert와 동시에 스코빌 지수가 낮은 순으로 자동 정렬될 수 있게 만들어 주고, 스코빌 지수가 낮은 두 음식을 섞을 함수를 따로 만들어 저장해주면 끝! 

사실 자료 구조만 잘 이해하고 있으면 정말 쉽게 풀 수 있는 문제다.

 

---

package com.choonham;

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        int count = 0;
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        
        for(int i= 0; i < scoville.length; i++) {
        	heap.add(scoville[i]);
        }
        
        
        while(true) {
        	if(heap.peek() >= K) {
        		answer = count;
        		break;
        	} else if(heap.size() == 1) {
        		answer = -1;
        		break;
        	}
        	heap.add(mix(heap.poll(), heap.poll()));
        	count++;

        }
        
        
        return answer;
    }
    
    
    public int mix(int first, int second) {
    	int mix = 0;
    	
    	mix = first + (second * 2);
    	
    	return mix;
    }
}

 

---