[Programmers] 더 맵게

Note : 이 글은 지극히 주관적인 생각을 토대로 작성된 글입니다. 혹시나 잘못된 부분이 있다면 메일 또는 코멘트를 통해 알려주시면 감사하겠습니다. 😄 제 메일은 About 탭에서 확인하실 수 있습니다. 📧

P.S : 이 페이지는 웹에 최적화 된 페이지입니다. 가급적 모바일이 아닌 웹에서 보시는 것을 추천드립니다.

문제 정보

• 문제 설명

  • 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K이상으로 만들고 싶습니다.

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

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

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

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

• 제한 사항

  • scoville의 길이는 1이상 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회입니다.

소스코드

• 문제 풀이 언어 : Java

import java.util.*;
import java.util.stream.*;

class Solution {
    public int solution(int[] scoville, int k) {
        int answer = 0;
        PriorityQueue<Integer> queue = IntStream.rangeClosed(0, scoville.length - 1)
                .map(i -> scoville[i]).boxed()
                .collect(Collectors.toCollection(PriorityQueue::new));

        while (queue.size() > 1 && queue.peek() < k) {
            queue.offer(queue.poll() + ((queue.isEmpty() ? 0 : queue.poll()) * 2));
            answer++;

            if (queue.stream().allMatch(i -> i >= k))
                break;
        }

        return Optional.ofNullable(queue.peek()).orElse(-1) < k ? -1 : answer;
    }
}