풀이_LC908.md

🧵 908. Smallest Range I

• Date : 2022.02.20(일)
• Time : 15분

Problem

• You are given an integer array nums and an integer k. In one operation, you can choose any index i where 0 <= i < nums.length and change nums[i] to nums[i] + x where x is an integer from the range [-k, k]. You can apply this operation at most once for each index i. The score of nums is the difference between the maximum and minimum elements in nums. Return the minimum score of nums after applying the mentioned operation at most once for each index in it.

Constraints

• 1 <= nums.length <= 5000
• 0 <= nums[i] <= 5000

Example

• Input: nums = [1,3,6], k = 3
• Output: 0
• Explanation: Change nums to be [4, 4, 4]. The score is max(nums) - min(nums) = 4 - 4 = 0.
  
  

풀이

    def smallestRangeI(self, nums: List[int], k: int) -> int:
        minScore = min(nums) + k
        maxScore = max(nums) - k
        if minScore > maxScore:
            return 0
        else:
            return maxScore - minScore

: 일단 우리는 배열의 값에 -k ~ +k 까지의 연산을 해줄 수 있다. 그런데 배열에서 최대 원소와 최소 원소의 차이가 제일 적으려면 어떻게 해야할까를 많이 고민했다. 그 답은 바로 최대 원소가 최대한 작아져야하고 최소 원소가 최대한 커져야 한다는 것이다. 그래서 두 값이 차이가 줄어들어서 차이가 적게 날 수 있다. 그렇기 때문에 nums의 최소값에는 최대 연산인 +k를 해주고, nums의 최대값에는 최소 연산인 -k를 행해주면 된다. 연산을 했더니 minScore가 더 커지는 경우가 있을 것이다. 이 경우는 배열에서 두 값을 동일하게 만들 수 있음을 의미하므로 0을 return 해준다.