945. Minimum Increment to Make Array Unique

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

 

이번주가 정렬 주간이었던 것 같은데, 이 문제 또한 선정렬 후 맞춰나가면 되는 문제다. 주어진 list 내 모든 숫자들이 unique하도록 만들면 되는 문제인데, 간단하게 겹치는 숫자들이 발생하면 한 쪽으로 쭉 밀면서 모두가 unique하도록 하는 최소 횟수를 찾으면 된다.

 

정렬을 했기 때문에 i번째 숫자는 i-1번째 숫자보다 크거나 같은 상황일텐데, 같은 상황일 때는 i번째 숫자를 i-1번째 숫자보다 1 큰 숫자로 밀어버리면 된다. 이 때 i+1번째 숫자가 i번째 숫자보다 작은 상황이 발생할 수도 있는데(초기 lst[i-1] == lst[i] == lst[i+1]), 이럴 때도 lst[i]보다 1 큰 숫자로 lst[i+1]을 밀어버리면 된다. 일반화 시키면 다음과 같이 코드를 짤 수 있다.

 

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

view raw Minimum Increment to Make Array Unique.py hosted with ❤ by GitHub