[ 자바스크립트(JavaScript) ] section07 - 12 - 마굿간 정하기(결정 알고리즘)

📍 section07 - 12 - 마구간 정하기(결정 알고리즘)

문제: N개의 마구간이 수직선상에 있다. 각 마구간은 x1, x2, x3, ..., xN 의 좌표를 가지며 마구간 간에 좌표가 중복되는 일은 없다. 현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않는다. 가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶다.

 

입력: 첫째줄에 자연수 N과 C의 공백을 사이에 두고 주어지고 둘째줄에 마구간의 좌표가 차례로 주어진다.

출력: 첫 줄에 가장 가까운 두 말의 거리를 출력하시오.

// 입력
5 3
1 2 8 4 9

// 출력
3

 

이 문제를 왜 Parametric Search 으로 풀어야 하는지 생각해보면, 가장 가까운 두 말의 거리가 최대가 될 때까지 최적의 해를 계속 찾아야 하기 때문이다. 예를 들어, 두 말의 거리(출력)가 2라고 가정하면, C마리의 말을 마구간의 좌표 내에 모두 배치할 수 있다. 하지만, 이것이 최적의 답인가?를 고민하면 그렇지 않다. 왜냐면 3도 마구간의 좌표 내에 모두 배치 할 수 있음과 동시에 가장 가까운 두 말의 거리가 최대가 되기 때문이다. 하지만, 4가 되면 수직선 상에 최대 2마리까지 밖에 배치할 수 없다. 이처럼 더 이상 해를 찾을 수 없을 때까지 계속 최적의 해를 갱신해야 하므로 Parametric Search를 이용해야한다. 보통 범위 내 조건을 만족하는 최소 / 최대 값을 찾는 문제거나, n의 값이 너무 크고 정렬을 통해 답을 찾는다면 Parametric Search를 이용하면 된다. 로직은 다음과 같다.

 

1. 가장 가까운 말의 거리를 찾을 때까지 최적의 해를 계속 갱신한다.

2. 주어진 좌표는 오름차순으로 정렬되어 있어야 말 사이의 거리를 구할 수 있다.

3. lt와 rt는 말 사이의 거리인데 lt는 말의 최소거리인 1이고, rt는 말의 최대거리인 arr[arr.length-1]이다.

4. 말 사이의 거리 (mid)가 가까울수록 말을 더 많이 배치할 수 있다. 이때, cnt(거리에 따라 배치한 말의 수)가 달라지게 되는데, 이때 c보다 같거나 크면 주어진 수직선 상에서도 말을 더 많이 배치할 수 있기 때문에 답이 될 수 있다. 하지만 c와 같지 않기 때문에 거리를 늘려서 탐색한다.(lt=mid+1) 반대로, cnt<c일 때는 말 사이의 거리를 너무 크게 잡아서 수직선 상에 말을 배치할 수 없기 때문에 거리를 좁혀야 한다. (rt=mid-1)

5. 거리를 더 이상 좁히거나 넓힐 수 없을 때 반복문을 종료한다.

 

 

728x90

 

let n = 5;
let c = 3;
let arr = [1, 2, 4, 8, 9];

console.log(solution(n, c, arr));

function solution(n, c, arr){
    arr.sort((a, b) => a-b);
    let lt = 1;
    let rt = arr[arr.length-1];
    let answer;

    while (lt <= rt){
        let mid = Math.floor((lt+rt)/2);
        let cnt=1;
        let endPoint = arr[0]

        for (let i=1; i<n; i++){
            if (arr[i]-endPoint >= mid){
                cnt++;
                endPoint=arr[i]
            }
        }

        if (cnt >= c){
            answer=mid;
            lt=mid+1;
        }else rt=mid-1

    }
    return answer;
}