[Java] LeetCode 910. Smallest Range II

[Java] LeetCode 910. Smallest Range II

 

문   제 : 

정수형 1차원 배열 nums와 정수 k가 주어진다.

nums[i]는 nums[i]-k 혹은 nums[i]+k 로 바꿀 수 있다.

위 상황을 가정했을 때 max(nums) - min(nums) 가 최소가 되게 하고 그 값을 구하여라.

 

{ 1 <= nums.length <= 10^4 }

{ 0 <= nums[i] <= 10^4}

{ 0 <= k <= 10^4 }

 

 

You are given an integer array nums and an integer k.

For each index i where 0 <= i < nums.length, change nums[i] to be either nums[i] + k or nums[i] - k.

The score of nums is the difference between the maximum and minimum elements in nums.

Return the minimum score of nums after changing the values at each index.

 

Example )

Input: nums = [1], k = 0
Output: 0
Explanation: 
The score is max(nums) - min(nums) = 1 - 1 = 0.

///////////////////////////////////////////////////////

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

 

---

접   근 : 

nums 배열을 정렬해서 최소 최대 값을 찾아주고, 그 후에 배열의 원소를 하나 씩 접근해서 결과값이 최소가 되게 하는 값을 도출한다.

 

 

---

해   결 : 

nums 배열을 정렬한다.

 

최대값-최소값이 k값보다 작으면 nums[i] 값을 아무리 바꿔도

그 값이 더 작아질 수 없으므로 그대로 리턴해준다.

 

첫 값을 잡고 반복문을 수행한다.

최소값에서 k값을 더한 값, 순회하고 있는 원소에서 k를 뺀 값  중 작은 값

순회하고 있는 원소에서 k를 더한 값, 최대값에서 k를 뺀 값 중 큰 값

위 두 값을 구하고 차이를 구하고 그 차이가 더 작다면 결과값을 업데이트 시켜준다.

 

---

nums 배열을 정렬해준다.

 

 

Arrays.sort(nums);

 

 

---

최대값-최소값이 k값보다 작으면 그대로 리턴해준다.

 

 

if(nums[n-1] - nums[0] <= k){
    return nums[n-1] - nums[0];
}

 

---

반복문을 수행한다.

 

 

int output = nums[n-1] - nums[0];
for(int i=1; i<n; i++){
    int min = Math.min(nums[0]+k, nums[i]-k);
    int max = Math.max(nums[i-1]+k, nums[n-1]-k);
    output = Math.min(output, max-min);
}

 

 

---

결   과  :

class Solution {
    public int smallestRangeII(int[] nums, int k) {
        int n = nums.length;
        if(n == 1) return 0;

        Arrays.sort(nums);

        if(nums[n-1] - nums[0] <= k){
            return nums[n-1] - nums[0];
        }

        int output = nums[n-1] - nums[0];
        for(int i=1; i<n; i++){
            int min = Math.min(nums[0]+k, nums[i]-k);
            int max = Math.max(nums[i-1]+k, nums[n-1]-k);
            output = Math.min(output, max-min);
        }
        return output;
        
    }
}