LeetCode 1552 Magnetic Force Between Two Balls

Medium

In the universe Earth C-137, Rick discovered a special form of magnetic force between two balls if they are put in his new invented basket. Rick has n empty baskets, the ith basket is at position[i], Morty has m balls and needs to distribute the balls into the baskets such that the minimum magnetic force between any two balls is maximum.

Rick stated that magnetic force between two different balls at positions x and y is |x - y|.

Given the integer array position and the integer m. Return the required force.

Example 1:

Input: position = [1,2,3,4,7], m = 3
Output: 3
Explanation: Distributing the 3 balls into baskets 1, 4 and 7 will make the magnetic force between ball pairs [3, 3, 6]. The minimum magnetic force is 3. We cannot achieve a larger minimum magnetic force than 3.

Example 2:

Input: position = [5,4,3,2,1,1000000000], m = 2
Output: 999999999
Explanation: We can use baskets 1 and 1000000000.

Constraints:

• n == position.length
• 2 <= n <= 105
• 1 <= position[i] <= 109
• All integers in position are distinct.
• 2 <= m <= position.length

문제해석

지구 C-137 우주에서 Rick은 새로 발명한 바구니에 두 개의 공을 넣으면 특별한 형태의
자기력이 발생한다는 것을 발견했습니다. Rick은 n개의 빈 바구니를 가지고 있으며,
i번째 바구니는 position[i] 위치에 있습니다. Morty는 m개의 공을 가지고 있으며,
공들 사이의 최소 자기력이 최대가 되도록 공을 바구니에 분배해야 합니다.
Rick은 두 개의 다른 공이 x와 y 위치에 있을 때 자기력은 |x - y|라고 말했습니다.
정수 배열 position과 정수 m이 주어질 때, 요구되는 자기력을 반환하세요.

 

해결방법

- 처음 주어진 순서는 중요하지 않다.

- 1 ~ 주어진 배열의 max 값 중에 정답이 있다

- 일일히 하나씩 다 확인하기에는 시초발생

- 이진탐색으로 정답이 되는지 판단하자!!

 

풀이

import java.util.*;

class Solution {
    public int maxDistance(int[] position, int m) {

        Arrays.sort(position);

        int max = 0;

        for(int i=0; i<position.length; i++){
            max = Math.max(max, position[i]);
        }

        int s = 1;
        int e = max;

        while(s <= e){

            int mid = (s+e) / 2;

            if(check(position, mid, m))
                s = mid + 1;
            else 
                e = mid - 1;

        }

        return e;
    }

    static boolean check(int[] arr, int force, int m){

        int cnt = 1;
        int tmp = arr[0];

        for(int i=1; i<arr.length; i++){

            if(arr[i] - tmp >= force){
                cnt++;
                tmp = arr[i];
            }

            if(cnt >= m) return true;

        }

        return false;

    }


}