baekjoon. 공유기 설치

문제

링크

2110번: 공유기 설치

풀이

단계별의 이분탐색 실버 문제들은 대부분 비슷한 것 같다

이 문제의 경우엔 첫 집과 마지막 집의 거리를 구해서 그 범위 내에서 이분 탐색을 진행하면 쉽게 풀 수 있다

테스트 케이스를 예로 들면

  1. 우선 배열을 정렬 한다 [1,2,4,8,9] 

  2. 공유기 설치의 간격으로 1과 9의 중간 값인 5를 정해서 공유기를 설치해본다

      2-1. 이 때 첫 집에 공유기를 설치했다고 가정하고 시작
    
      2-2. 거리가 2와 4인 집은 5보다 간격이 적기 때문에 건너뛰고 8인 집에 설치한다

  3. 설치한 공유기의 개수가 C보다 적으면 공유기 설치 간격을 줄이고 많으면 늘린다

이 과정을 반복하는 코드를 짜주면 된다

코드

    function solution(input){
        input = input.split('\n');

        const C = input[0].split(' ')[1]*1;
        const arr = [];

        for(let i=1;i<input.length;i++){
            arr.push(input[i]*1);
        }

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


        console.log(binarySearch(arr,C));

    }
    function binarySearch(arr, C){
        let min = 1;
        let max = arr[arr.length-1];

        while(min<=max){
            const mid = Math.floor((min+max)/2);

            const cnt = getCnt(mid, arr);

            if(cnt>=C){
                min = mid+1;
            } else max = mid-1;
        }
        return min-1;
    }
    function getCnt(value, arr){
        let house = arr[0];
        let cnt = 1;
        for(let i=1; i<arr.length;i++){
            const dist = arr[i] - house;
            if(dist>=value){
                cnt++;
                house = arr[i];
            }
        }
        return cnt;
    }