[leetcode][945] Minimum Increment to Make Array Unique

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

---

A 배열을 오름차순 정렬한다.

그리고 unique한 값을 저장하는 변수를 하나 만든다.

unique한 값의 초기값은 A배열에서 가장 작은 값과 같고

A배열을 탐색해갈수록 1씩 커진다.

A배열을 앞에서부터 탐색할 때,

unique 값이 A[i]값보다 같거나 작다면 unique 값은 A[i]로 갱신시켜준다. (오름차순 정렬을 했고 조건이 1을 더하는 것이므로 1을 더해서 이후에 유니크한 값을 만드려면 현재 탐색 중인 값보다는 반드시 커야한다.)

unique 값이 A[i] 값보다 크다면 A[i]는 unique값이 되기위해 값을 더해야 한다. 이 값이 정답에 더해진다. (ex. unique 값이 4이고 A[i]가 1인 경우 4가되기 위해 3이 더해야 한다.)

[3, 2, 1, 2, 1, 7] 을 예로 들어보자.

먼저 오름차순 정렬

[1, 1, 2, 2, 3, 7]. uniqueNum = 1 이다.

i	A[i]	uniqueNum	answer
0	1	1	0
1	1	2	1 (+1)
2	2	3	2 (+1)
3	2	4	4 (+2)
4	3	5	6 (+2)
5	7	7	6

시간 복잡도는 |A| = N이라 했을 때, O(NlogN).

---

소스코드 : https://gist.github.com/fpdjsns/896094e66db6c064e75b79fff17a9139