[LeetCode] 945. Minimum Increment to Make Array Unique

https://leetcode.com/problems/minimum-increment-to-make-array-unique/description/

leetcode - Minimum Increment to Make Array Unique

문제 유형 : 정렬, 그리디

문제 난이도 : Medium

 

문제

You are given an integer array nums. In one move, you can pick an index i where 0 <= i < nums.length and increment nums[i] by 1.

Return the minimum number of moves to make every value in nums unique.

The test cases are generated so that the answer fits in a 32-bit integer.

 

정수 배열 nums를 받는다.

i를 골라 nums[i]를 1 증가시키는 연산을 1회씩 할 수 있습니다.

nums의 모든 요소가 하나씩만 있도록 연산하는 최소 횟수를 구하시오.

integer 범위내로 보장됩니다.

 

풀이

배열을 정렬하고, 인덱스 1부터 n-1까지 다음을 검사한다:

만약 현재 인덱스가 이전 인덱스의 값보다 작거나 같으면, (두 수의 차 + 1)만큼 현재 배열과 ans에 누적시킨다.

 

ans를 반환한다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int minIncrementForUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        int n = nums.size();
        int ans = 0;
        for(int i = 1; i < n; i++) {
            if(nums[i] <= nums[i-1]) {
                int x = (nums[i-1] - nums[i])+1;
                nums[i] += x;
                ans += x;
            }
        }
        return ans;
    }
};