Minimum Increment to Make Array Unique

문제 번호, 이름: 945. Minimum Increment to Make Array Unique

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

날짜: 2024/06/14

상태: 완료

 

이 문제를 고른 이유

리트코드 오늘의문제

문제 보고 처음 든 생각

카페 자리가 좁아서 종이에 써가며 풀 수가 없어서 머리로만 풀려니 부담감이 있었다

처음 든 생각.. sort를 할까 counting을 할까.. 비어있는 숫자를 어떻게 빨리 찾을 수 있을까..

 

풀이 v1

• 소요 시간 11분 (이 중 고민에 6분?)

wrong answer

 

from collections import Counter

class Solution:
    def minIncrementForUnique(self, nums: List[int]) -> int:
        num_counts = Counter()
        for num in nums:
            num_counts[num] += 1

        answer = 0
        waiting_numbers = 0
        for checknum in range(100001):
            answer += waiting_numbers
            if checknum not in num_counts:
                if waiting_numbers > 0:
                    num_counts[checknum] = 1
                    waiting_numbers -= 1
                continue
            elif num_counts[checknum] == 1:
                continue
            else:
                waiting_numbers += (num_counts[checknum] - 1)

        return answer

 

비어 있는 숫자를 빨리 찾을 필요는 없었다. 그냥 차례로 숫자를 키워가며 그 숫자가 몇갠지, 비어있는지를 한꺼번에 처리했다.

위 코드는 checknum의 range를 [0, 10^5+1) 로 잡고 있는데, nums에 10^5만 10^5개 있는 edge case를 생각해보면 [?, 2 * 10^5 + 1) 까지 잡아야 했다는걸 금방 떠올릴 수는 있었다.

근데 그렇게 막 숫자 늘려가며 푸는게 맞는건가? 아닐 거 같아서 다른 방법 찾아보았다

(나중에 남들 풀이를 보니까 이게 맞았다.. 하지만 항상 20만을 도는 건 아니고, n과 max_num에 따라 유동적으로)

 

풀이 v2

• 소요 시간 추가7분

from collections import Counter

class Solution:
    def minIncrementForUnique(self, nums: List[int]) -> int:
        num_counts = Counter()
        for num in nums:
            num_counts[num] += 1

        answer = 0
        waiting_numbers = 0
        checknum = 0
        n = len(nums)
        while n > 0 or waiting_numbers > 0:
            answer += waiting_numbers
            if checknum not in num_counts:
                if waiting_numbers > 0:
                    waiting_numbers -= 1
            elif num_counts[checknum] == 1:
                n -= 1
            else:
                waiting_numbers += (num_counts[checknum] - 1)
                n -= num_counts[checknum]
            
            checknum += 1
            

        return answer

 

num_counts를 n에서 차감해가며 숫자를 다 봤는지 아닌지를 세기로 했다.

근데 숫자를 다 보긴 했어도 아직 자리를 못 찾은 중복숫자가 남아있을 수 있으니까 waiting_numbers 가 0보다 큰지도 같이 while 조건에 넣어 확인했다

 

다른 사람 풀이를 보니까 방향은 이게 맞고 시간복잡도 O(N)도 최적이 맞는데 예시코드를 그대로 복붙해서 넣으면 속도도 빠르고 메모리도 적게 쓰는데, 내 코드는 안 그렇다.. 풀이 v1을 n과 max_len 넣어서 수정해봐도 느리다. 어느 부분에서 내 코드만 느려진 건지 잘 안 찾아진다

 

이 문제를 풀고 얻은 것

• 문제 조건을 따져서 숫자를 하드코딩 하는 것을 무조건 나쁘게 보지 말자!
  20만을 하드코딩 하는게 최종 해결책은 아니었지만, 그걸 왠지 나쁜 방법이라고 생각하는 바람에 그 다음으로 못 넘어간 게 아닐까 싶다. 중간 단계로써는 숫자 하드코딩도 좋은 방법일 수 있다

메모

• 오랜만에 medium인데 5분 넘게 풀이 방향이 안 떠오른 문제