[HackerRank] Jesse and Cookies

Problem

---

Jesse loves cookies and wants the sweetness of some cookies to be greater than value k. To do this, two cookies with the least sweetness are repeatedly mixed. This creates a special combined cookie with:

sweetness = (1 × Least sweet cookie  + 2 × 2nd least sweet cookie).

This occurs until all the cookies have a sweetness ≥ k.

Given the sweetness of a number of cookies, determine the minimum number of operations required. If it is not possible, return -1.

 

Example
k = 9

A = [2, 7, 3, 6, 4, 6]

The smallest values are 2, 3.
Remove them then return 2 + 2 × 3 = 8 to the array. Now A = [8, 7, 6, 4, 6].
Remove 4, 6 and return 4 + 6 × 2 = 16 to the array. Now A = [16, 8, 7, 6].
Remove 6, 7, return 6 + 2 × 7 = 20 and A = [20, 16, 8, 7].
Finally, remove 8, 7 and return 7 + 2 × 8 = 23 to A. Now A = [23, 20, 16].
All values are ≥ k = 9 so the process stops after 4 iterations. Return 4.

 

Function Description
Complete the cookies function in the editor below.

cookies has the following parameters:

• int k: the threshold value
• int A[n]: an array of sweetness values

Returns

• int: the number of iterations required or -1

Input Format

The first line has two space-separated integers, n and k, the size of A[] and the minimum required sweetness respectively.

The next line contains n space-separated integers, A[i].

 

Constraints

1 ≤ n ≤ 10^6

0 ≤ k ≤ 10^9

0 ≤ A[i] ≤ 10^6

Sample Input

STDIN               Function
-----               --------
6 7                 A[] size n = 6, k = 7
1 2 3 9 10 12       A = [1, 2, 3, 9, 10, 12]

Sample Output

2

Explanation

Combine the first two cookies to create a cookie with sweetness  = 1× 1 + 2 × 2 = 5
After this operation, the cookies are 3, 5, 9, 10, 12.
Then, combine the cookies with sweetness 3 and sweetness 5, to create a cookie with resulting sweetness  = 1 × 3 + 2 × 5 = 13
Now, the cookies are 9, 10, 12, 13.
All the cookies have a sweetness ≥ 7.

Thus, 2 operations are required to increase the sweetness.

---

Jesse는 쿠키를 좋아하며, 모든 쿠키의 단맛이 특정 값 k보다 커지기를 원합니다. 이를 위해, 단맛이 가장 낮은 두 개의 쿠키를 반복적으로 섞습니다. 이때, 섞인 쿠키의 단맛은 다음과 같이 계산됩니다:

새로운 단맛=(1×가장 단맛이 낮은 쿠키 + 2×두 번째로 단맛이 낮은 쿠키)

이 과정은 모든 쿠키의 단맛이 k 이상이 될 때까지 반복됩니다.

주어진 쿠키의 단맛 배열에서, 모든 쿠키의 단맛이 k 이상이 되기 위한 최소 작업 수를 계산하세요. 만약 불가능하다면 -1을 반환하세요.

 

예제

k = 9, A = [2, 7, 3, 6, 4, 6]

1. 가장 작은 값 2와 3을 선택하여 새로운 단맛 8을 생성한 후 배열에 추가합니다. A = [8, 7, 6, 4, 6]
2. 4와 6을 선택하여 새로운 단맛 16을 생성하여 배열에 추가합니다. A = [16, 8, 7, 6]
3. 6과 7을 선택하여 새로운 단맛 20을 생성하여 배열에 추가합니다. A = [20, 16, 8, 7]
4. 마지막으로 7과 8을 선택하여 새로운 단맛 23을 생성하여 배열에 추가합니다. A = [23, 20, 16]

모든 값이 k = 9 이상이므로, 총 4번의 작업이 필요합니다. 정답은 4입니다.

 

함수 설명

public static int cookies(int k, List<Integer> A)

• 매개변수
  • int k: 최소 요구 단맛 값
  • List<Integer> A: 쿠키의 초기 단맛 값을 담은 배열
• 반환값
  • int: 최소 작업 수 또는 불가능할 경우 -1

 

 

728x90

 

 

 

Solution

---

import java.util.*;

public class Solution {

    public static int cookies(int k, List<Integer> A) {
        // 최소 힙(우선순위 큐) 생성
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(A);

        int operations = 0;

        // 가장 작은 값이 k 이상이 될 때까지 반복
        while (minHeap.size() > 1 && minHeap.peek() < k) {
            // 가장 단맛이 낮은 두 쿠키 추출
            int leastSweet = minHeap.poll();
            int secondLeastSweet = minHeap.poll();

            // 새로운 단맛 계산
            int newSweetness = leastSweet + 2 * secondLeastSweet;

            // 새로운 쿠키를 힙에 추가
            minHeap.add(newSweetness);

            // 작업 수 증가
            operations++;
        }

        // 모든 쿠키의 단맛이 k 이상인지 확인
        return minHeap.peek() >= k ? operations : -1;
    }

}

 

1. 최소 힙 생성:
   • PriorityQueue<Integer> minHeap = new PriorityQueue<>(A);를 사용해 쿠키의 단맛을 최소 힙으로 관리하여 가장 낮은 단맛 두 개를 쉽게 추출합니다.
2. 반복문:
   • minHeap.size() > 1 && minHeap.peek() < k 조건을 만족하는 동안 계속 반복합니다. 이는 최소 두 개의 쿠키가 남아있고, 가장 낮은 단맛이 k보다 작을 때까지 실행합니다.
3. 새로운 단맛 계산 및 추가:
   • minHeap.poll()로 단맛이 가장 낮은 두 쿠키를 추출하여 새로운 단맛을 계산한 후, 이를 힙에 다시 추가합니다.
4. 결과 반환:
   • 모든 쿠키의 단맛이 k 이상이라면 작업 수 operations를 반환하고, 그렇지 않다면 -1을 반환합니다.

복잡도 분석

• 시간 복잡도: O(n log n), 힙의 삽입과 삭제가 로그 시간(log n)에 수행되며, 평균적으로 n번의 삽입 및 삭제가 발생합니다.
• 공간 복잡도: O(n), PriorityQueue가 배열을 복사하여 관리하므로 추가 공간이 필요합니다.

---

이 코드에서는 모든 쿠키의 단맛을 k 이상으로 만들기 위해 필요한 최소 작업 수를 계산합니다. 이 문제를 해결하기 위해 최소 힙을 사용하는데, 최소 힙을 통해 단맛이 가장 낮은 두 개의 쿠키를 빠르게 선택할 수 있기 때문입니다.

 

1. PriorityQueue란 무엇인가?

PriorityQueue는 우선순위 큐의 일종으로, 기본적으로 가장 낮은 값이 항상 맨 앞에 오도록 정렬된 큐입니다. 최소 힙으로 동작하며, 값이 삽입되거나 삭제될 때마다 자동으로 정렬됩니다.

• 사용 시점: 우선순위가 있는 항목을 빠르게 접근할 때 사용합니다. 여기서는 단맛이 가장 낮은 쿠키 두 개를 선택하기 위해 PriorityQueue를 사용했습니다.
• 효율성: 가장 작은 값이나 가장 큰 값을 빠르게 추출할 수 있어 반복적으로 최소값을 찾는 문제에 적합합니다.

2. 코드 분석

PriorityQueue<Integer> minHeap = new PriorityQueue<>(A);

 

• 설명: PriorityQueue<Integer> minHeap = new PriorityQueue<>(A);는 A 리스트의 모든 요소를 우선순위 큐로 복사하여 최소 힙을 만듭니다. 이렇게 하면 자동으로 리스트가 작은 값부터 정렬된 상태로 큐에 삽입됩니다.
• 목적: minHeap에서 항상 가장 낮은 단맛의 쿠키를 빠르게 선택할 수 있습니다.

    int operations = 0;

 

• 설명: operations는 단맛을 높이는 데 필요한 작업 수를 기록하기 위한 변수입니다.

    // 가장 작은 값이 k 이상이 될 때까지 반복
    while (minHeap.size() > 1 && minHeap.peek() < k) {

• 설명: while문은 큐에 최소 두 개의 쿠키가 남아 있고, 가장 낮은 쿠키의 단맛이 k 미만인 경우에 반복됩니다.

3. peek() 메서드

• peek()는 큐의 맨 앞 요소(즉, 가장 작은 단맛의 쿠키)를 반환합니다.
• 큐에서 값을 제거하지 않고 확인만 하므로 이후 작업에서 제거할 필요가 없는 경우에 유용합니다.
• 사용 위치: while문 조건에 사용되며, 단맛이 k 이상인지 확인합니다.

4. poll() 메서드

• poll()은 큐의 맨 앞 요소를 반환하고, 그 요소를 큐에서 제거합니다.
• 사용 이유: 가장 낮은 단맛의 두 쿠키를 선택하여 큐에서 제거하고, 새로운 단맛의 쿠키를 추가하기 위해 사용됩니다.