[LeetCode#2517] Maximum Tastiness of Candy Basket

 

❐ Description

---

이번 문제는 Binary Search + Greedy로 해결하는 문제였다.

백준으로 치면 실버1~골드4 사이의 난이도

 

이번 문제에서 문제의 조건이 단조성을 가지기 때문이다. 단조성은 특정 조건이 증가하거나 감소함에 따라

결과가 변하지 않고 일정한 방향으로 변화하는 성질을 의미한다. 

 

이와 유사한 문제로 최근에 풀어본 [Path With Minimum Effort] 문제가 있다.

 

 

 

 

 

❐ 접근 방식

---

1. 이분 탐색을 위해 주어진 price 배열을 오름차순 정렬한다.
2. 이분 탐색 초기화 
   • 최솟값(0)과 최댓값(price 배열 내 최대값 - 최소값) 사이에서 탐색하며 가능한 최적의 답을 찾는다.
3. 이분 탐색 수행
   • 중간 값 mid를 계산하고, tastiness가 mid일 때 k개의 사탕을 선택할 수 있는지 확인한다.
   • 선택이 가능하다면, tastiness를 더 크게 설정할 수 있으므로 left = mid + 1로 탐색한다.
   • 선택이 불가능하다면, tastiness를 줄여야 하므로 right = mid - 1로 탐색한다.
4. 주어진 tastiness 값이 유효한지 확인하는 함수를 작성한다.
   • 정렬된 배열을 순차적으로 탐색하며, 최소 차이가 mid 이상인 경우에만 사탕을 선택한다.
5. 최적의 tastiness 반환

 

 

 

 

 

❐ Solution

---

public class Solution {

    public int maximumTastiness(int[] price, int k) {
    
        // Step1. 이분 탐색을 위해 주어진 price 배열을 오름차순 정렬한다. 
        Arrays.sort(price);

        // Step2. 이분 탐색 초기화
        int left = 0;
        int right = price[price.length - 1] - price[0];
        int result = 0;
        
        // Step3. 이분 탐색 수행
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (isValid(price, k, mid)) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        // Step5. 최적의 tastiness 반환
        return result;
    }
    
    // Step4. 주어진 tastiness 값이 유효한지 확인하는 함수
    private boolean isValid(int[] price, int k, int mid) {
        int count = 1;
        int prev = price[0];
        
        for (int i = 0; i < price.length; i++) {
            if (price[i] - prev >= mid) {
                count++;
                prev = price[i];
                if (count == k) return true;
            }
        }
        return false;
    }
}

 

 

 

 

 

---