[LeetCode] 1402. Reducing Dishes - Java/Dart

https://leetcode.com/problems/reducing-dishes/description/

Reducing Dishes - LeetCode

---

문제

A chef has collected data on the satisfaction level of his n dishes. Chef can cook any dish in 1 unit of time.

Like-time coefficient of a dish is defined as the time taken to cook that dish including previous dishes multiplied by its satisfaction level i.e. time[i] * satisfaction[i].

Return the maximum sum of like-time coefficient that the chef can obtain after dishes preparation.

Dishes can be prepared in any order and the chef can discard some dishes to get this maximum value.

 

Example 1:

Input: satisfaction = [-1,-8,0,5,-9]
Output: 14
Explanation: After Removing the second and last dish, the maximum total like-time coefficient will be equal to (-1*1 + 0*2 + 5*3 = 14).
Each dish is prepared in one unit of time.

Example 2:

Input: satisfaction = [4,3,2]
Output: 20
Explanation: Dishes can be prepared in any order, (2*1 + 3*2 + 4*3 = 20)

Example 3:

Input: satisfaction = [-1,-4,-5]
Output: 0
Explanation: People do not like the dishes. No dish is prepared.

 

Constraints:

• n == satisfaction.length
• 1 <= n <= 500
• -1000 <= satisfaction[i] <= 1000

---

풀이

풀이 과정

요리사가 만드는 요리의 만족도가 담긴 배열 satisfaction이 주어지고 하나의 요리를 준비하는데 1만큼의 시간이 소요된다. 이때  요리사가 요리를 준비하는데 필요한 Like-time coefficient 값의 최대합을 구하는 문제이다.

문제에서 요구하는 Like-time coefficient는 n번째 요리를 준비할 때 현재까지 요리를 준비하는데 걸리는 시간과 현재 요리의 만족도의 곱을 의미한다. 예를 들어 3번째로 준비하는 요리의 만족도가 3이라면 이 요리의 Like-time coefficient는 3(시간) x 3(만족도) = 9가 된다. 따라서 n개의 요리를 준비할 때 각 요리의 Like-time coefficient 값의 합이 최대가 되는 값을 구하면 된다.

요리를 준비하는 순서는 상관이 없으며 최대값을 만들기 위하여 요리를 제외시키는 것도 가능하다.

풀이 과정은 다음과 같다.
먼저 요리의 만족도가 담겨있는 배열 satisfaction를 오름차순으로 정렬하여 큰 값 부터 낮은 값 순으로 탐색한다.
n번째 까지의 음식의 만족도의 합을 갱신하며 최대값에 더해나간다.
단 n번째 까지의 음식의 만족도의 합이 0 이하가 되는 경우 이 지점부터는 최대값이 줄어들게 되므로 그 지점에서의 최대값을 return한다.
탐색이 끝까지 종료되는 경우에도 마찬가지로 최대값을 return 해준다.

---

최종 코드

• Java

class Solution {
    public int maxSatisfaction(int[] satisfaction) {
        // 최종적으로 반환할 최대값
        int maxSum = 0;
        
        // satisfaction 배열을 오름차순으로 정렬
        Arrays.sort(satisfaction);
        
        // 가장 높은 만족도 값이 음수인 경우 음식을 준비할 필요가 없으므로 0을 바로 return
        if(satisfaction[satisfaction.length - 1] < 0) return 0;
        
        // 지금까지 탐색한 각 음식의 만족도의 합
        int sum = 0;
        
        // 마지막 인덱스 부터 반대로 탐색
        for(int i = satisfaction.length -1; i >= 0; i--) {
            // 현재 음식의 만족도를 합계에 추가
            sum += satisfaction[i];
            
            // 현재까지 음식의 만족도의 합이 음수가 되는 경우
            // 이 지점부터는 최대값이 줄어들게 되므로 현재까지 탐색한 최대값을 return
            if(sum <= 0)  return maxSum;
            // 현재까지 음식의 만족도의 합이 양수가 되는 경우
            // 최대값에 만족도의 합을 추가
            else maxSum += sum;
        }

        return maxSum;
    }
}

• Dart

class Solution {
  int maxSatisfaction(List<int> satisfaction) {
    // 최종적으로 반환할 최대값
    var maxSum = 0;
    
    // satisfaction 리스트를 오름차순으로 정렬
    satisfaction.sort();
    
    // 가장 높은 만족도 값이 음수인 경우 음식을 준비할 필요가 없으므로 0을 return
    if(satisfaction[satisfaction.length - 1] < 0) return 0;
    
    // 지금까지 탐색한 각 음식의 만족도의 합
    var sum = 0;
    
    for(var i = satisfaction.length - 1; i >= 0; i--){
        // 현재 음식의 만족도를 합계에 추가
        sum += satisfaction[i];
        
        if(sum <= 0) return maxSum;
        else maxSum += sum;
    }
    
    return maxSum;
  }
}

---