본문 바로가기
알고리즘 문제/Leetcode

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

by 햄과함께 2018. 11. 27.
320x100

문제 : 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

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

320x100

댓글