[Leetcode]- weekly contest 341 (Minimize the Maximum Difference of Pairs)

 

You are given a 0-indexed integer array nums and an integer p. Find p pairs of indices of nums such that the maximum difference amongst all the pairs is minimized. Also, ensure no index appears more than once amongst the p pairs.

Note that for a pair of elements at the index i and j, the difference of this pair is |nums[i] - nums[j]|, where |x| represents the absolute value of x.

Return the minimum maximum difference among all p pairs. We define the maximum of an empty set to be zero.

 

https://leetcode.com/problems/minimize-the-maximum-difference-of-pairs/description/

 

 

Constraints: (Brute Force로 접근시, Timeout이 자명함)

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^9
• 0 <= p <= (nums.length)/2

 

 

Hint 1

페어를 구하는데 있어서, 주어진 숫자의 순서는 상관이 없다.

 

Hint 2

숫자들의 순서가 보장되어 있으므로, 이진 탐색을 이용할 수 있다.

 

Hint 3

만약 값 (페어의 차이)이 원하는 답이고,  해당 값보다 페어 간 차이가 작다는 것은, 각 페어들이 실제 구하고자 하는 pair 범주안에 든다 생각할 수 있다.

 

 

Approach

 

1. 답을 도출하는데 숫자 순서에 영향을 받지 않으므로, 정렬한다.

 

var minimizeMax = function(nums, p) {
    nums.sort((a,b) => a-b);
}

 

2. 정답 후보는, 최소(서로 같은 값인 페어간 차인) 0 부터 최대 (가장 작은 요소와 가장 큰 요소간 차) nums[last] - nums[0] 이다.

var minimizeMax = function(nums, p) {
    nums.sort((a,b) => a-b);
    const n = nums.length - 1;
    let start = 0;
    let end = nums[n] - nums[0];
}

 

3. 이진 탐색을 통해 원하는 목표값 (즉, pair 가 p가 되는 최솟값)을 찾는다.

var minimizeMax = function(nums, p) {
    nums.sort((a,b) => a-b);
    const n = nums.length - 1;
    let start = 0;
    let end = nums[n] - nums[0];
    
    while(start < end){
    	// 당연하지만, 정수간 차가 소수일리 없으므로, 내림 처리.
    	let mid = Math.floor((start+end)/2);
        
        //isPairResolved함수를 통해, 인자로 주어지는 mid(임계값, 해당값 이하에서, 몇개의 pair가 생성되는지 체크)
      	const validation = isPairResolved(mid);
       	if(validation){
        	//현재값보다 작은 페어가 p개 이상 생성된다. 목표값은 현재값 혹은 현재값보다 작다.
        	end = mid;
        }else{
        	// 현재값 보다 작은 페어가 p개보다 적게 생성된다. 목표값은 현재값보다 커야한다.
        	start = mid + 1;
        }
    }
}

4. isPairResolved: 인자값보다 작은 페어가 몇개 생성되는지 체크한다.

 

 

var minimizeMax = function(nums, p) {
    nums.sort((a,b) => a-b);
    const n = nums.length - 1;
    let start = 0;
    let end = nums[n] - nums[0];
    
    
    function isPairResolved(threshold){
    	let resolvedPair = 0;
        let i = 1;
        while(i <= n){
        	const diff = nums[i] - nums[i-1];
            
            if(diff <= threshold){
            	i += 2; // 페어라는 뜻은, 당연하지만, 요소 두개로 이루어져있으므로
                resolvedPair ++;
            }else{
            	i ++;
            }
            if(resolvedPair === p){
            	return true;
            }
        }
        
        return false;
    
    }
    while(start < end){
    	let mid = Math.floor((start+end)/2);
      	const validation = isPairResolved(mid);
       	if(validation){
        	end = mid;
        }else{
        	start = mid + 1;
        }
    }
    
    
    return start
}