LeetCode - Minimum Increment to Make Array Unique

문제 설명

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.

입출력 예시

Example 1:

Input: nums = [1,2,2]
Output: 1
Explanation: After 1 move, the array could be [1, 2, 3].

Example 2:

Input: nums = [3,2,1,2,1,7]
Output: 6
Explanation: After 6 moves, the array could be [3, 4, 1, 2, 5, 7].
It can be shown with 5 or less moves that it is impossible for the array to have all unique values.

제약사항

1 <= nums.length <= 105
0 <= nums[i] <= 105

Solution

[전략]
0. input 배열 원소중 최대 값을 찾고,
1. 최대값만큼의 배열을 별도로 만들어서 input 각 배열의 원소 값를 index로 하여 frequency를 count함
2. frequency 배열을 순회하며 각 frequency 값을 1만 남기고 나머지는 다음 index의 frequency로 이관
=> 각 숫자가 unique 하게 존재해야하므로 index별 frequency를 하나만 남기고 나머지의 것들은 1씩 더하며 중첩해나감
3. 배열의 max값까지 순회한 후, max+1에 중첩된 나머지 frequency들에 대해
각 숫자별 frequency가 하나씩 존재하도록 moves 함

class Solution {
    public int minIncrementForUnique(int[] nums) {

        if (nums.length < 2) {
            return 0;
        }
        int maxVal = nums[0];
        for (int i = 1; i < nums.length; i++) {
            maxVal = Math.max(maxVal, nums[i]);
        }

        int[] freqNum = new int[maxVal + 2];

        for (int i = 0; i < nums.length; i++) {
            freqNum[nums[i]]++;
        }

        int increaseCount = 0;
        for (int i = 0; i <= maxVal; i++) {
            if (freqNum[i] > 1) {
                int increaseVal = freqNum[i] - 1;
                increaseCount += increaseVal;
                freqNum[i + 1] += increaseVal;
            }
        }
        for (int i = 1; i < freqNum[maxVal + 1]; i++) {
            increaseCount += i;
        }
        return increaseCount;
    }
}