프로그래머스 Lv2 더 맵게

weonest·2023년 4월 23일

coding-test

목록 보기

29/36

문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

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

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

scoville의 길이는 2 이상 1,000,000 이하입니다.
K는 0 이상 1,000,000,000 이하입니다.
scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

입출력 예

scoville	K	return
[1, 2, 3, 9, 10, 12]	7	2

입출력 예 설명

스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]
스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

나의 풀이

문제의 가장 큰 힌트는 문제의 분류에 있었다. 이번 문제의 분류는 Heap으로 분류되어 있는데, 이는 메모리 영역의 Heap이 아닌 완전 이진 트리의 Heap이다.

Heap의 특징

중복값을 허용한다

완전 이진 트리이다

설정한 우선순위를 바탕으로 가장 우선시되는 값을 root node로 두며, 자동으로 정렬이 이루어진다

Java에서 내부적으로 Heap을 사용하는 자료구조는 PriorityQueue가 있다. 즉, 이번 문제는 PriorityQueue를 사용하여 풀면 된다는 것이다.

이번 문제부터 IDE 사용을 자제할 겸 프로그래머스 Solution 창에서만 코드를 작성하여 문제를 풀어보았다.

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;

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

        for (int i : scoville) {
            pq.offer(i);
        }
        int min = pq.peek();
        while (K > min && pq.size() > 1) {
            answer++;

            int least = pq.poll();
            int less = pq.poll();
            int hotter = least + (less * 2);
            pq.offer(hotter);

            min = pq.peek();
        }
            if (min < K) return -1;

        return answer;
    }
}