[Leetcode] 2195. Append K Integers With Minimal Sum

https://leetcode.com/problems/append-k-integers-with-minimal-sum/description/

어떤 배열이 주어지고, 해당 배열에 없는 정수를 k개 만큼 추가하는데 그 추가하는 정수의 합이 최소가 되도록 하는 문제이다.

배열에 있는 정수를 딕셔너리에 저장하고 1부터 시작해서 숫자가 거기에 있는 지 탐색하면서 없다면 답을 더하는 방식으로 풀었다.

from collections import defaultdict

class Solution:
    def minimalKSum(self, nums: List[int], k: int) -> int:
        numbers = defaultdict()

        for n in nums:
            numbers[n] = True
        return numbers
        i = 1
        answer = 0
        while k:
            if i not in numbers:
                answer += i
                k -= 1
            i += 1

        return answer

그리고 또 틀렸다;;;

nums = [1000000000]
k = 1000000000

인 경우에 대해서 시간초과가 났다. 1억번에 대해서 비교하는게 O(n)이라 괜찮다 싶었는데 아니었나보다.

힌트 3번에서 1부터 k까지의 합으로 시작해보라고 했는데 거기에 착안하여 1부터 k까지의 합을 구하고 k보다 작은 nums안에 있는 숫자를 빼면서 k++를 더해가는 방식으로 가야겠다.

class Solution:
    def minimalKSum(self, nums: List[int], k: int) -> int:
        nums = sorted(list(set(nums)))
        numbers = set(nums)

        answer = k*(k+1)//2
        a = k
        print(nums)
        for n in nums:
            if n > k:
                break
            
            a += 1
            while a in numbers:
                a+=1
            print(answer, n, a, a - n)
            answer += a - n

        return answer

nums안에 중복이 없다는 조건이 없기에 set으로 중복제거하고 정렬해줬다. 그리고 O(1)의 탐색을 위해 numbers라는 집합을 만들어줬다.

앞의 설명대로 k까지의 합을 구하고, k보다 작은 nums안의 숫자를 빼면서 nums안에 없는 k보다 큰 수를 더해줬다.