[JS] 백준 2110번 공유기 설치

---

문제 링크

https://www.acmicpc.net/problem/2110

풀이 전략

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

코드 

const fs = require("fs");
const input = fs
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split(/\s/)
    .map(Number);

const n = input.shift(); // 사용하지 않는다.
const c = input.shift();

solution(input);

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

    while (lt <= rt) {
        const mid = ~~((lt + rt) / 2);

        if (calDis(arr, mid) >= c) lt = mid + 1;
        else rt = mid - 1;
    }

    console.log(rt);
}

function calDis(arr, mid) {
    let cnt = 1;
    let curPos = arr[0];

    for (const pos of arr) {
        if (pos - curPos >= mid) {
            cnt++;
            curPos = pos;
        }
    }

    return cnt;
}

 

회고

집의 좌표가 0과 1,000,000,000사이인 것을 보고 이분탐색을 떠올렸다. 조금 더 범위가 작았더라면 다른 알고리즘을 떠올릴 수 있겠지만 넓은 범위를 탐색하기 위해서는 이분 탐색만큼 빠른 것은 찾아 보기 힘들기에 이분탐색으로 문제를 풀기로 하였다. 

어떤 알고리즘을 사용할지 결정을 하였다면 이에 따라 구현하는 것은 그리 어렵지 않았다. 

 

더 좋은 방법이나 의견이 있으시다면 댓글 부탁드립니다 :)