프로그래머스 더 맵게 자바 풀이

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

코딩테스트 연습 - 더 맵게

우선 순위 큐를 이용하는 문제.

 

우선순위 큐는 Integer 오브젝트를 담을 때는 기본적으로 숫자가 작은 것이 우선순위가 높게 책정된다.

큰 숫자가 우선순위가 높도록 하려면 아래 처럼 코드를 작성하면 된다.

 

PriorityQueue<Integer> pq = new PriorityQueue<>(Collentions.reverseOrder());

 

논리 자체는 어렵지 않았으나, 예외는 -1로 리턴해주는 부분이 떠오르질 않아서 찾아봤다. (이걸 해주지 않으면 계속 몇 개의 테케는 런타임에러가 났다. while문에서 빠져나갈 수 없기 때문!)

-1을 retrun 해주는 경우는 더이상 스코빌지수를 K이상으로 올릴 수 없을 때, 즉 2개가 있다면 그 두개를 합쳐 한 개가 되어도 그 수가 K를 넘지 않을 때이다. 따라서 pq.size()가 1이지만 아직 while문을 돌고 있을 때 -1을 return 해주면 된다.

 

import java.util.*;

class 더_맵게 {
    public int solution(int[] scoville, int K) {

        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();

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

        int fst, snd, newS;

        while(pq.peek() < K) {

            if(pq.size() == 1) return -1;

            answer ++;
            fst = pq.poll();
            snd = pq.poll();

            newS = fst + snd * 2;

            pq.offer(newS);
        }

        return answer;
    }
}