[LeetCode] 1509. Minimum Difference Between Largest and Smallest Value in Three Moves

https://leetcode.com/problems/minimum-difference-between-largest-and-smallest-value-in-three-moves/description/

leetcode - Minimum Difference Between Largest and Smallest Value in Three Moves

문제 유형 : 그리디, 정렬, 슬라이딩 윈도우

문제 난이도 : Medium

 

문제

You are given an integer array nums.

In one move, you can choose one element of nums and change it to any value.

Return the minimum difference between the largest and smallest value of nums after performing at most three moves.

 

정수 배열 nums가 주어진다.

한 번의 Move에 당신은 한 숫자의 값을 변경할 수 있다.

최대 3번의 move끝에 나오는 가장 작은 최대값과 최소값의 차를 구하시오.

 

풀이

만약 요소가 4개 이하이면, 3개의 수를 나머지 하나에 맞추면 된다. 즉, 무조건 0이 나온다.

그게 아니라면, 3개를 제외한 n-3개의 숫자를 비교하면 되는데, 

정렬된 배열에서 [0, n-4], [1, n-3], [2, n-2], [3, n-1]의 구간에서 가장 최소 차를 구하면 된다.

 

코드

C++

class Solution {
public:
    int minDifference(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        if(n <= 4) return 0;
        int res = INT_MAX;

        res = min(res, nums[n-1] - nums[3]);
        res = min(res, nums[n-2] - nums[2]);
        res = min(res, nums[n-3] - nums[1]);
        res = min(res, nums[n-4] - nums[0]);
        
        return res;
    }
};