[LeetCode] #1887. Reduction Operations to Make the Array Elements Equal

✏️ 문제

Given an integer array nums, your goal is to make all elements in nums equal. To complete one operation, follow these steps:
Find the largest value in nums. Let its index be i (0-indexed) and its value be largest. If there are multiple elements with the largest value, pick the smallest i.Find the next largest value in nums strictly smaller than largest. Let its value be nextLargest.Reduce nums[i] to nextLargest.
Return the number of operations to make all elements in nums equal.

 

🤖 알고리즘

 

#배열  #정렬

 

 

🤯 풀이 방법

 

풀었는데도.. 뭐라고 설명해야 할지 모르겠다

1, 3, 5를 같게 만들려면 5 > 3, 3 > 1, 3 > 1 이렇게 세번 하면 다 1로 같아지게 할 수 있다

정렬을 이용해서 풀었는데, 테케에 주어진 [1, 1, 2, 2, 3]을 보면 (이미 정렬되어있지만)

가장 작은 1보다 한 단계 큰 수인 2는 두 개, 두 단계 큰 수인 3은 한 개 있다.

그러면 1 * 2, 2 * 1을 더한 4가 답이 된다.

그런 식으로 다음 단계로 커지는 숫자가 나타날 때마다 단계를 표시해서 더해 주는.. 방식

정렬하고 한바퀴 돌면 된다

시간대는 90%였는데 메모리가 늘 어렵다 흠

 

👾 구현 코드 (자바)

class Solution {
    public int reductionOperations(int[] nums) {
        Arrays.sort(nums);
        int ans = 0;
        int start = 0;
        int cur = nums[0];
        
        for (int n : nums) {
            if (n > cur) {
                cur = n;
                start++;
            }
            ans += start;
        }
        
        return ans;
    }
}