[Java] 프로그래머스 Lv.2 : 더 맵게

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

코딩테스트 연습 - 더 맵게

 

풀이

우선순위 큐(Priority Queue)를 사용한다.

낮은 숫자가 우선순위인 int 형 우선순위 큐를 선언하고 큐에 스코빌지수를 넣어준다.

첫번째 heap의 요소가 K이상이 될 때까지 반복문을 돌린다.

• 앞의 두 음식을 꺼내(pop) 새로운 음식으로 만들어 다시 heap에 넣어준다.(pull)
• 가장 앞의 음식의 스코빌 지수가 K이상이 되면 break
• 만약 heap의 요소가 1개일떄는 -1을 return해준다.

import java.util.PriorityQueue;
import java.util.Collections;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        //낮은 숫자가 우선 순위인 int 형 우선순위 큐 선언
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        // 큐에 스코빌지수 넣음
        for(int s : scoville){
            heap.add(s);
        }

        while(heap.peek()<K){
            // 앞의 두 음식을 섞어서(pop) 새롭게 만들어 저장
            heap.add(heap.poll() + heap.poll()*2);
            answer++; // 섞은 횟수 증가

            // 가장 앞의 음식의 스코빌 지수가 K이상이 되면 break
            if(heap.peek() >= K) break;
            if(heap.size()==1 && heap.peek()<K) return -1;
        }

        return answer;
    }
}