[LeetCode] 1552. Magnetic Force Between Two Balls

https://leetcode.com/problems/magnetic-force-between-two-balls/description/

leetcode - 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.

 

Rick은 자기력의 특별한 힘을 보았다.

Rick은 n개의 빈 바구니가 있고, i번째 바구니는 position[i]에 있다.

m개의 공이 있고 두 공 사이의 자기력들 중 최대값이 최소가 되도록 공을 분산시켜야 한다.

 

두 위치의 차만큼이 자기력이다.

position이라는 정수배열과 정수 m이 주어진다. 최소 힘을 구하시오.

 

 

풀이

처음에는 인덱스0과 인덱스 n-1에 두 공을 놓고 이진탐색으로 두 공 사이에 놓을 곳을 균일하게 배분해보려고 했는데, 

문제는 계속해서 가장 큰 차가 나는 부분에 공을 놓고 분할해야 한다는 건데, 그게 안된다는 거다.

솔루션의 도움을 받았는데, 이진탐색의 범위를 "거리"로 하는것이다.

low = 1, high = position에서 가장 큰 값과 가장 작은값의 차이 / m-1로 설정하고,

 

이진탐색으로 mid = (low + high)/2로 하면, mid가 각 m개의 공들의 분산거리이다.

이제 이 mid가 가능한지 확인한다. 배열에 인덱스 1부터해서 mid의 간격만큼 m개이상 놓을 수 있는지 검사하는 것이다.

가능하면 ans에 mid를 갱신하고, low = mid+1, 불가능하면 right-1을 해서 가능하면 더 큰 인터벌로 시도해보고, 안되면 더 작은 범위에서 시도하도록 시키는것이다.

 

코드

C++

class Solution {
    int n;
public:
    int isAble(int dist, int m, vector<int>& position) {
        int balls = 1;
        int last = position[0];
        for(int i = 1; i < n; i++) {
            if(position[i] - last >= dist) {
                balls++;
                last = position[i];
            }
            if(balls >= m) {
                return true;
            }
        }
        return false;
    }

    int maxDistance(vector<int>& position, int m) {
        n = position.size();
        sort(position.begin(), position.end());
        int low = 1;
        int high = (position[n-1] - position[0]) / (m-1);
        int ans = 0;
        while(low <= high) {
            int mid = (low + high)/2;
            if(isAble(mid, m, position)) {
                ans = mid;
                low = mid+1;
            } else {
                high = mid-1;
            }
        }
        return ans;
    }
};