[LeetCode] Minimize the Maximum Difference of Pairs 자바

문제 (이분탐색)

 

Minimize the Maximum Difference of Pairs - LeetCode

 

 

문제 풀이

 

문제 해석 자체도 어려워서 많이 헤매었다.

구하고자 하는 문제를 정리해보자면

1. p개의 쌍 추출 ← 이때 쌍의 두 원소 차는 최소가 되어야 함

2. 그 중 최댓값 return

 

처음엔 정렬하여 두개씩 짝지어 차를 구해 p개를 추출해 최대를 반환하였는데, 두개씩 짝지을 때 생각해야하는 부분이 생각보다 많았다.

최소의 차를 가지는 쌍을 지을 때 그 나머지도 최소가 되어야하기 때문에 이 부분을 생각하는게 까다로운 것 같다. 그래서 결국 구글링을 통해 이분탐색으로 푸는 것을 깨달았다. 이 문제를 이분탐색으로 풀 생각은 전혀 나지않았는데 왜 하필 완탐이 아니라 이분탐색일까 생각해보았는데, 나올 수 있는 답이 정해져 있기 때문이다. (답의 범위가 nums가 가지는 조건 최대값보다 훨씬 작음)

 

 

소스 코드

 

class Solution {
    public int minimizeMax(int[] nums, int p) {
        Arrays.sort(nums);

        int ans = 0;
	int low = 0;	//최소차
	int high = nums[nums.length-1] - nums[0];	//최대차
		
	while(low <= high) {
		int mid = (high + low) / 2;
			
		if(isPossible(nums, p, mid)) {	//해당 mid가 최대차로 가능할 경우
			ans = mid;
			high = mid - 1;
		}
		else
			low = mid + 1;
	}
		
	return ans;
	}
	
	public boolean isPossible(int nums[],int p,int mid){
        	boolean flag = true;
		int count = 0;
		
		for(int i = 1; i < nums.length; i++) {
			if(!flag) {         //한텀 뛰어넘게 만드는 장치
				flag = true;
				continue;
			}
			
			if(nums[i] - nums[i-1] <= mid) {
				count++;
				flag = false;
			}
		}
		
		return count >= p;
    }
}