[인프런 코딩테스트] 마구간 정하기, 결정 알고리즘 (feat. 이분탐색 응용, javascript)

1. 문제

N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ......, xN의 좌표를 가지며, 마 구간간에 좌표가 중복되는 일은 없습니다. 현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다. 각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다.  C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대 값을 출력하는 프로그램을 작성하세요.

 

첫 줄에 자연수 N(3<=N<=200,000)과 C(2<=C<=N)이 공백을 사이에 두고 주어집니다. 둘째 줄에 마구간의 좌표 xi(0<=xi<=1,000,000,000)가 차례로 주어집니다.

 

첫 줄에 가장 가까운 두 말의 최대 거리를 출력하세요.

 

 

2. 풀이

function count(stable, dist) {
    let cnt = 1, ep = stable[0]
    for (let i = 1; i < stable.length; i++) {
        if (stable[i] - ep >= dist) {
            cnt++;
            ep = stable[i]
        }
    }


    return cnt;
}
function solution(c, stable) {
    let answer;
    stable.sort((a, b) => a - b);

    let lt = 1;
    let rt = stable[stable.length - 1];

    while (lt <= rt) {
        let mid = ~~((lt + rt) / 2);
        //말 3마리 들어갈 수 있는지 체크 
        if (count(stable, mid) >= c) {
            answer = mid;
            lt = mid + 1
        } else rt = mid - 1
    }

    return answer;
}

let arr = [1, 2, 8, 4, 9];
console.log(solution(3, arr));

 

위 문제는 이분탐색을 응용하여 푸는 문제이다.

 

우선 문제를 해석해보면, C마리의 말을 N개의 마구간에 넣었을 때, 가장 가까운 두 말의 거리가 최대가 되는 값을 구하면 된다.

각 마구간의 좌표는 배열의 형태로 주어지고, 마구간에는 한 마리의 말만 들어갈 수 있다. 

 

우리가 구해야 할 것은 가장 가까운 두 말의 거리가 최대가 되는 값, 즉 마구간 사이의 최대 거리이므로 

이분탐색의 기준을 마구간 사이의 거리로 두어야 한다. 

 

그리고 해당 거리만큼 벌려서 말을 마구간에 넣었을 때, 들어갈 수 있는지 체크하면서 범위를 좁혀 나가면 된다. 

코드를 차례대로 해석해보자.

 

stable.sort((a, b) => a - b);

 

마구간의 좌표는 x1, x2, x3... 형태로 주어진다.

마구간의 위치가 차례로 들어온다는 보장이 없기 때문에 좌표에 맞게 sort를 통해 정렬해 준다. 

 

 

let lt = 1;
let rt = stable[stable.length - 1];

 

lt, rt를 통해 이분탐색의 범위를 지정할 것이다.

우리가 구해야 할 것은 마구간의 거리이므로 각각 마구간의 최소거리, 최대거리가 들어간다.

 

따라서 lt는 마구간의 최소거리인 1이 들어가고, rt는 마구간의 최대거리인 정렬된 배열의 맨 마지막 값이 들어간다.

(맨 마지막 값 = 가장 큰 값)

 

 

while (lt <= rt) { 
    let mid = parseInt((lt + rt) / 2); 
    ....
}

 

이제 while문을 통해 마구간의 최대 거리를 구해보자.

while은 lt가 rt와 값이 같아지거나, 더 커질 때까지 반복해 준다.

 

mid는 중간에 있는 값을 가져와야 하기 때문에, lt+rt 한 값을 2로 나눠준다.

무조건 자연수여야 하기 때문에 parseInt를 통해 소수점은 없애준다.

 

 

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

 

마구간의 거리가 mid일 때, N마리의 말들이 들어갈 수 있는지 체크해 준다.

count 함수에선 마구간의 거리가 mid일 때 들어갈 수 있는 말이 몇 개인지 리턴할 것이다.

따라서 해당 값이 마구간에 넣어야 할 말의 개수(c)와 비교해 준다. 

 

우선, 함수 count는 나중에 작성하고, 다음 코드부터 살펴보자.

 

만일, 마구간의 거리가 mid일 때, N마리의 말이 들어갈 수 있으면 answer은 mid가 된다.

그러나 이 값이 최상인지는 lt와 rt가 만날 때까지 확인해 봐야 하기 때문에 lt의 값을 옮겨주고, 계속해서 마구간의 거리를 측정해야 한다.

 

우리가 구해야 하는 것은 가장 거리가 먼 경우이기 때문에 mid보다 큰 경우가 있는지 찾아야 한다.

따라서 이때 lt의 값은 mid+1이 된다.

 

만일, 마구간의 거리가 mid일 때, N마리의 말이 들어갈 수 없다면, rt의 범위를 바꿔준다.

현재 mid 이후의 값은 모두 답이 될 수 없으므로 mid-1을 rt에 넣어준다. 

 

 

function count(stable, dist) {
    let cnt = 1, ep = stable[0] 
    for (let i = 1; i < stable.length; i++) {
        if (stable[i] - ep >= dist) {
            cnt++;
            ep = stable[i]
        }
    }
    return cnt;
}

 

이제 mid에 N마리의 말이 들어갈 수 있는지 체크해 보자.

 

우선, N마리의 말이 들어갔는지 체크하기 위해서 cnt 변수를 만들어주고

마지막으로 마구간에 넣은 말의 위치를 체크하기 위해 ep 변수를 만들어 준다.

 

좌표상 가장 첫 번째 마구간에 말을 넣는 것이 유리하기 때문에

cnt의 기본값은 1, ep의 기본값은 stable의 첫 번째 값이 된다. 

 

이후 다음 마구간(stable[i]) - 현재 마구간(ep)의 거리가 체크해야 할 마구간의 거리(dist) 보다 크거나 같다면

말을 넣을 수 있으므로 cnt를 ++해주고, 마지막으로 말을 넣은 마구간의 좌표(ep)를 현재 좌표(stable[i])로 바꿔준다.

 

 

---

 

진짜 지금까지 강의들으면서 이게 제일 어려웠던거 같다ㅠㅠ

결정 알고리즘이 어떻게 문제를 풀어야 할지 감이 안와서 계속해서 문제를 읽기만 했던거 같다.

그래도 이렇게 글로 정리하니까 생각이 정리된 느낌.. 

나중에 다시 한 번 풀어봐야겠다!