[알고리즘]프로그래머스 42626번 - 더 맵게

프로그래머스 42626번 - 더 맵게

프로그래머스 42626번 - https://programmers.co.kr/learn/courses/30/lessons/42626

 

요구사항

1. 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞는다.

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

3. 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을, 그렇지 않을 경우 섞은 최소 횟수를 반환

 

요구사항 분석 및  풀이과정

섞은 음식의 스코빌 지수는 가장 맵지 않은 음식의 스코빌 지수와 두 번째로 맵지 않은 음식의 스코빌 지수로 구성되었다는 것을 통해서 우리는 모든 음식의 스코빌 지수를 오름차순으로 정렬할 필요가 없다는 것을 알 수 있습니다.

 

첫 번째로 맵지 않은 음식, 두 번째로 맵지 않은 음식의 스코빌 지수만 알면 되므로, 힙 자료구조 최적이라는 것을 알 수 있습니다.  따라서 저는 우선순위 큐를 사용하여 첫 번째로 맵지 않은 음식과 두 번째로 맵지 않은 음식의 스코빌 지수만을 가져올 것입니다.

 

힙 정렬은 약한(Weak) 정렬 또는 느슨한 정렬이라고 불리며, 가장 큰 원소 또는 작은 원소가 힙의 루트에 존재한다는 것만을 보장합니다.

 

소스코드 작성

import java.util.stream.Collectors;
import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> pq = Arrays.stream(scoville).boxed()
            .collect(Collectors.toCollection(PriorityQueue::new));

        int result = 0;
        
        while (pq.size() > 1 && pq.peek() < K) {
            int first = pq.poll();
            int second = pq.poll();
            pq.offer(first + 2 * second);
            result++;
        }
        
        return pq.peek() < K ? -1 : result;
    }
}

결과

소스코드 깃허브 주소

링크