[2024] day 167. Leetcode 945. Minimum Increment to Make Array Unique

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 6월 14일 (금)
Leetcode daily problem

945. Minimum Increment to Make Array Unique

https://leetcode.com/problems/minimum-increment-to-make-array-unique/?envType=daily-question&envId=2024-06-14

Problem

정수 배열 nums가 제공 될때, 한 번의 이동으로 0 <= i < nums.length인 인덱스 i를 선택하고 nums[i]를 1씩 증가시킬 수 있다.

nums의 모든 값을 고유하게 만들기 위한 최소 이동 횟수를 반환한다.

테스트 케이스는 답변이 32비트 정수에 맞도록 생성된다.

Solution

Sorting

주어진 정수 배열 nums의 모든 원소가 서로 다른 값이 되기 위해서 동일한 숫자가 여러번 발생하면 해당 숫자를 증가시켜야 한다.
그러기 위해서 배열을 오름 차순으로 정렬하고, 배열을 순회하면서 중복되는 값을 찾고 중복이 발생하면 값을 증가 시켜 다음 위치로 이동시킨다.
중복되는 값을 처리하면서 필요한 증가 연산 횟수를 누적한다.

Code

class Solution:
    def minIncrementForUnique(self, nums: List[int]) -> int:
        nums.sort()
        ans = 0
        
        for i in range(1, len(nums)):
            if nums[i] <= nums[i-1]:
                added = nums[i-1] - nums[i] + 1
                nums[i] += added
                ans += added
                
        return ans

Complexicity

시간 복잡도

주어진 배열을 정렬하는데 O(nlogn) 이 소요되고,
해당 배열을 한 번 순회하므로 O(n)이 소요된다.
즉 전체 시간 복잡도는 O(nlogn) + O(n)이다.

공간 복잡도

배열을 정렬하면서 O(n) 추가 공간을 사용하여, 총 공간복잡도는 O(n)이다.