99클럽 코테 스터디 24일차 TIL Leetcode Append K Integers With Minimal Sum

나의 접근

1. O(N)의 시간 복잡도로 nums 배열을 하나씩 체크하면서 간격 사이에 있는 숫자들을 k가 충족 될때까지 한번에 합을 구하는 방식을 사용했다.

2. 시작할때 중복된 값을 제거 후 정렬을 진행하여 수가 큰 경우 낭비되는 runtime을 줄였다.

3. while문 이후에 더 코드를 작성하면 더러워 보여서, 제한사항인 10**9이 끝이므로 10**9+1을 추가하여, while문으로 정답을 구할 수 있도록 작성하였다.

나의 코드

class Solution:
    def minimalKSum(self, nums: List[int], k: int) -> int:
        nums.append(10**9+1)
        nums=sorted(set(nums))
        start=0
        answer=0
        count=0
        i=0
        while count<k:
            end=nums[i]
            if 0<end-start-1<=k-count:
                count+=end-start-1
                answer+=(end-start-1)*(start+end)//2
            elif end-start-1>k-count:
                answer+=(k-count)*(start*2+k-count+1)//2
                count=k
            i+=1
            start=end
        return answer

코드 회고

- 다른 사람들의 풀이를 보니 nums 배열을 순회하며, 초기 k값 + 뺴야하는 배열의 수를 갱신하며, n>k가 되는 경우 1에서 k까지의 합을 구한뒤, 해당된 nums의 값들을 저장한 s값을 뺀 풀이가 있었다.

- 다시 말하면, 임의의 수 x가 있을때 1에서 x 사이에 있는 nums에 있는 값들을 제외하면 k개가 되는 경우를 구하면 되는 것이었다. 수학적인 접근 방법이 인상 깊었던 풀이였다.