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

https://leetcode.com/problems/reduction-operations-to-make-the-array-elements-equal/description/

Reduction Operations to Make the Array Elements Equal - LeetCode

leetcode - Reduction Operations to Make the Array Elements Equal

문제 유형 : 정렬

문제 난이도 : Medium

 

문제

Given an integer array nums, your goal is to make all elements in nums equal. To complete one operation, follow these steps:

1. 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.
2. Find the next largest value in nums strictly smaller than largest. Let its value be nextLargest.
3. Reduce nums[i] to nextLargest.

Return the number of operations to make all elements in nums equal.

 

정수 배열 nums가 주어진다. 당신의 목표는 모든 요소들을 같게 만드는 것이다.

한 번의 연산을 수행하려면, 다음의 과정을 거쳐라.

 

1. nums에서 가장 큰 값을 찾아라. i(0-indexed에서)의 값이 가장 크다고 해보자.

만약 가장 큰 값이 여러 개라면, 가장 작은 i를(앞의 인덱스를)골라라.

2. 가장 큰 수 다음으로 큰 수를 찾아라. 이를 nextLargest라고 하자. nextLargest는 작거나 같은 게 아닌, 엄격하게 작아야 한다.

3. nums[i]를 nextLargest라고 하라.

 

 

풀이

[1, 3, 5]가 있다고 해보자. 1은 가장 작은 수이기에 놔두면 되고, 3은 1로 만들려면 한 번의 연산을,  5는 1로 만들려면 두 번의 연산을 취하면 된다.

 

오름차순 정렬을 통해서 연산 숫자를 누적시키는데, 현재 탐색하는 숫자가 이전 인덱스의 숫자와 다르면 취하는 연산 숫자를 1씩 키우면 된다.

 

 

코드

C++

class Solution {
public:
    int reductionOperations(vector<int>& nums) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);

        const int n = nums.size();
        int opsCount = 0;
        int ops = 0;

        sort(nums.begin(), nums.end());

        for(int i = 1; i < n; i++) {
            if(nums[i] != nums[i-1]) ops++;
            opsCount += ops;            
        }
        return opsCount;
    }
};