[프로그래머스] 프로그래머스 Level2 더 맵게 Java

문제

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

코딩테스트 연습 - 더 맵게

풀이

우선순위 큐를 사용하여 문제를 해결할 수 있었다.

매개변수 scoville의 모든 원소를 우선순위 큐에 집어넣으면 오름차순 형태의 데이터 집합이 만들어지는데

우리의 목적은 모든 음식들을 K 이상의 스코빌 지수로 만들어주는 것이기 때문에 우선순위 큐 앞에 있는 값이 낮은 원소들을 끌어와 연산해주면 되는 것이다.

하지만 배열처럼 인덱스로 바로바로 뽑아올 수 없기 때문에 우선순위 큐의 poll() 메서드를 이용하여 우선순위 큐의 맨 앞의 값을 가져오고 해당 원소를 삭제 시켜주는 행위를 두 번 반복하여 가장 맵지 않은 음식의 스코빌 지수와 두 번째로 맵지 않는 음식의 스코빌 지수를 가져와 연산해주면 섞은 음식을 만들 수 있다.

섞은 음식은 다시 우선순위 큐에 들어가면서 오름차순 정렬이 되므로 이러한 행위를 우선순위 큐의 가장 맨 앞 원소의 값이 K 보다 크거나 같을 때까지 반복하면서 카운트를 세주면 정답을 구할 수 있다.

주의할 점은 위 패턴을 반복하다 우선순위 큐의 크기가 1이 되버리면 poll() 메서드를 두 번씩 사용하는 이 코드에선 런타임 에러가 발생할 수 있기 때문에 모든 음식의 원소를 K 이상으로 만들지 못한다고 간주하고 -1을 리턴하면 문제를 해결할 수 있다.

 

코드

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {

        int answer = 0;

        PriorityQueue<Long> pq = new PriorityQueue<>();

        for(int i = 0; i < scoville.length; i++) {
            pq.add((long) scoville[i]);
        }

        while (true) {

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

            Long firstFood = pq.poll();
            Long secondFood = pq.peek();
            Long newFood = firstFood + (secondFood * 2);

            pq.poll();
            pq.add(newFood);
            answer++;

            if(pq.peek() >= K) {
                break;
            }
        }
        return answer;
    }
}