945. Minimum Increment to Make Array Unique

Given an array of integers A, a move consists of choosing any A[i], and incrementing it by 1.

Return the least number of moves to make every value in A unique.

 

Example 1:

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

Example 2:

Input: [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.

 

Note:

1. 0 <= A.length <= 40000
2. 0 <= A[i] < 40000

---

 

배열이 주어지고, 각 배열의 요소에 1씩 더하게끔 해서 배열내의 요소에 중복된 정보가 없도록 해야한다.

 

요점은 1씩 더한다는것이다. 1씩 빼야하는경우도 생긴다면 매우 복잡해 지겠지만

 

다행히 더하는것만 있어서 풀이가 간편해젔다.

 

작은값부터 시작하여 오름차순으로 값들에 접근하면서 얼마나 더할지를 알아내면 된다.

 

이를위해 counting sort에서 발상을 얻은 풀이를 이용하였다.

 

class Solution {
public:
    int minIncrementForUnique(vector<int>& A) {
        int N = A.size();
        if(N == 0)
            return 0;
        
        sort(A.begin(), A.end());
        int maxNum = A[0];
        int ret = 0;
        for(int i=1; i<N; i++){
            if(maxNum >= A[i]){
                ret += maxNum - A[i] + 1;
                A[i] += maxNum - A[i] + 1;                
            }
            maxNum = max(maxNum, A[i]); 
        }
        return ret;
    }
};

 

sort를 통해 오름차순으로 정렬함과 동시에 같은값들을 한군데에 모았다.

 

앞서 말했듯이 1씩 더할수만 있다는게 매우 중요하다.

 

maxNum은 이전에 수정된 값들중 최대값이 된다.

 

이 maxNum과 현재 순회중인 배열 요소를 비교하여 maxNum이 크다면 A[i]를 수정해야 하므로 그 차만큼 더해주면 된다.

 

이런발상으로 풀이를 접근하면

 

정렬시간(N * logN) + 순회시간(N)

 

만큼의 시간이 걸린다.

 

효율은 76ms에 87.98% 만큼의 시간 효율을 지닌다.

 

나쁘진 않지만 최적은 아니다.

 

 

 

여기서 우리는 정렬을 제외함으로써 시간복잡도를 보다 줄이는 방법을 선택할 수 있다.

 

선형으로 순회하면서 dictionary처럼 각 숫자가 들어있는 갯수를 파악한 후에

 

다시한번 선형순회를 하면서 답을 구하면 된다.

 

class Solution {
public:
    int minIncrementForUnique(vector<int>& A) {
        int N = A.size();
        int ret = 0;
        
        int imax = -1;  //배열 A내의 최대 원소값
        for(int i=0; i<N; i++)
            imax = max(A[i], imax);
        
        vector<int> vi(imax + 1, 0);
        
        for(int i=0; i<N; i++){
            vi[A[i]]++;
        }     
        
        int maxNum = -1;
        int diff =0;
        int from,to, sum;
        for(int i=0; i<= imax; i++){
            if(maxNum >= i){
                diff = maxNum - i + 1;
                maxNum += vi[i];
            }
            else{
                diff = 0;
                maxNum = max(maxNum, i + vi[i] - 1);
            }
            
            from = diff;
            to = diff + vi[i] - 1;
            
            sum = ((to + from) * vi[i]) / 2;
            ret += sum;
           
        }
        
        return ret;
    }
};

 

구현에 매우 신중해야한다.

 

56ms에 97.46 이라는 만족스러운 성능이 나왔다.

 

우선순위큐와 flag를 이용해서 크기가 1이상인 숫자를 넣어서 접근하는 방법도 있지만

 

이러면 정렬을 쓰지 않으면서 생긴 이점이 많이 줄어들게 된다.

 

그리고 주목할점은 이 문제에서 값의 범위와 배열 길이가 40000이하이기에

 

전자보다 후자가 더 나은 성능을 가진다는것이다.

 

만약 숫자의 범위가 수십억의 범위를 가진다면 후자의 케이스가 높은 성능을 가지기는 힘들것이다.