Jesse and Cookies

출처 : 해커 랭크

난이도 : 중간

알고리즘 : 우선순위 큐

 

 

제시는 쿠키를 좋아하고 쿠키의 단맛이 가치보다 더 높기를 원합니다.이를 위해 단맛이 가장 적은 쿠키 두 개를 반복적으로 섞습니다. 이렇게 하면 다음과 같은 요소들이 결합된 특별한 쿠키가 만들어집니다.

단맛 = (1 x  가장 단맛이 적은 쿠키 + 2 x 2번째로 단맛이 적은 쿠키 ).

이것은 모든 쿠키가 달콤해질 때까지 발생합니다. ≥ k.

쿠키 개수의 단맛을 고려하여 필요한 최소 연산 수를 결정하세요. 만약 불가능하다면 다음을 반환하세요. -1.

예
k = 9

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

가장 작은 값은 2, 3.
제거한 후 다시 돌려주세요 2 + 2 x 3 = 8 배열에. 지금 A = [8, 7, 6, 4, 6].
제거하다 4, 6 그리고 돌아오다 4 + 6 x 2 = 16배열에. 지금 A = [16 , 8, 7, 6].
제거하다 6, 7, 반품 6 + 2 x 7 = 20 그리고 A = [20, 16, 8, 7].
마지막으로 제거 8, 7 그리고 돌아오다 7 + 2 x 8 = 23에게 A. 지금 A = [23, 20, 16].
모든 값은 ≥k = 9그래서 그 과정은 다음에 멈춘다4 반복. 반환 4.

기능 설명 아래 편집기에서 쿠키
기능을 완료하세요 .

쿠키 에는 다음과 같은 매개변수가 있습니다.

• int k: 임계값
• int A[n]: 단맛 값의 배열

보고

• int: 필요한 반복 횟수 또는 -1

입력 형식

첫 번째 줄에는 공백으로 구분된 두 개의 정수가 있습니다. n그리고 k, 크기A[]그리고 각각 최소한으로 필요한 단맛.

다음 줄에는 다음이 포함됩니다. n공백으로 구분된 정수A[i].

제약 조건

1 ≤ n ≤ 10^6
0 ≤ k ≤ 10^9

0 ≤ A[i] ≤ 10^6

샘플 입력

STDIN 함수
----- --------
6 7 A[] 크기 n = 6, k = 7
1 2 3 9 10 12 A = [1, 2, 3, 9, 10, 12]  

샘플 출력

2

설명

첫 번째 두 개의 쿠키를 합치면 달콤한 쿠키가 완성됩니다. = 1 x 1 + 2 x 2 = 5
이 작업 후 쿠키는 3, 5, 9, 10, 12.
그런 다음 쿠키와 단맛을 결합합니다.그리고 달콤함, 결과적으로 단맛이 나는 쿠키를 만들기 위해 = 1 x 3 + 2 x 5 =13
이제 쿠키는 9, 10, 12, 13.
모든 쿠키에는 단맛이 있습니다 ≥ 7.

따라서, 2단맛을 높이기 위한 작업이 필요합니다.

 

 

----------------------------------------------------------------------------------------------------------------------------

 

문제 해독

모든 쿠키의 가치가 정해진 가치보다 높아지지 위해 몇번의 쿠기 재가공이 필요한지 구하는 문제

재가공시 가공한 쿠키의 가치 = 가치가 가장 낮은 쿠키 + 2 * 두번째로 가치가 낮은 쿠키

 

문제접근

전달받은 쿠키의 가치를 우선순위 큐에 가치의 순서대로 우선순위를 할당하여 가치가 낮은 쿠키가 우선순위가 높게 배치하고 우선순위가 가장 높은 쿠키가 정해진 가치보다 낮을경우 조합하여 높은 가치의 쿠기로 재가공하여 우선순위큐에 재할당 하여 우선순위가 가장 높은 쿠키의 수치가 정해진 가치보다 높아질때까지 반복합니다.

 

public static int cookies(int k, List<int> A)
    {
        if(A.Count == 0) return -1;
        
        PriorityQueue<int, int> q = new PriorityQueue<int, int>();
        foreach(int cookie in A)
            q.Enqueue(cookie, cookie);
            
        int minCookie = 0;
        while(q.Count > 1 && q.Peek() < k)
        {
            int first = q.Dequeue();
            int seconde = q.Dequeue();
            int newCookie = first + (seconde * 2);
            q.Enqueue(newCookie, newCookie);
            minCookie++;
        }
        return q.Peek() >= k ? minCookie : -1;
    }