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

문제 설명

 

코딩테스트 연습 - 더 맵게

 

접근 방법

해당 문제는 우선수위 큐 PriorityQueue 자료구조를 이용해서 해결할 수 있었습니다. 우선 처음 파라미터로 받은 int형 배열 scoville의 요소들을 PriorityQueue에 add합니다. 이때 PriorityQueue의 특성으로 add된 정수형 요소들은 오름차순으로 정렬되게 됩니다. (PriorityQueue 자료구조를 생성할 때 Collections.reverseOrder()를 인자로 주면 내림차순으로 정렬하도록 만들 수 있습니다.)

 

        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int s : scoville) {
            queue.add(s);
        }

 

PriorityQueue 자료구조의 peek() 메서드를 이용하면 첫 번째 인덱스에 해당하는 내부 요소 값을 참조할 수 있는데 만일 이 값이 파라미터로 받은 스코빌 지수 K 보다 같거나 크다면 음식을 섞을 필요가 없으므로 바로 0을 결과값으로 반환해줍니다.

 

        int result = 0;
        if (queue.peek() >= K) {
            return result;
        }

 

이후 PriorityQueue 자료구조의 크기가 2 이상일 경우 첫 번째 음식과 두 번째 음식을 poll 하여 섞은 후(새로운 스코빌 지수 값을 얻은 후) 이를 다시 PriorityQueue 자료구조에 add 합니다. 마찬가지로 이 값을 add할 때 내부적으로 오름차순으로 정렬이 일어나게 됩니다. 다시 peek() 메서드를 이용하여 K와 비교한 이후 K와 같거나 크다면 작업을 종료시키고 그렇지 않다면 PriorityQueue 자료구조의 크기가 2 미만일 때까지 앞선 작업을 반복해줍니다.

 

        int result = 0, firstNoHot, secondNoHot, mixedScoville;

        while (queue.size() > 1) {
            result++;
            firstNoHot = queue.poll();
            secondNoHot = queue.poll();

            mixedScoville = firstNoHot + (secondNoHot * 2);
            queue.add(mixedScoville);
            if (queue.peek() >= K) break;
        }

 

 

전체 소스 코드

import java.util.PriorityQueue;

class Solution {

    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();

        for (int s : scoville) {
            queue.add(s);
        }

        int result = 0, firstNoHot, secondNoHot, mixedScoville;
        if (queue.peek() >= K) {
            return result;
        }

        while (queue.size() > 1) {
            result++;
            firstNoHot = queue.poll();
            secondNoHot = queue.poll();

            mixedScoville = firstNoHot + (secondNoHot * 2);
            queue.add(mixedScoville);
            if (queue.peek() >= K) break;
        }

        return queue.peek() >= K ? result : -1;
    }
}

 

 

참고자료

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