마구간 정하기(결정 알고리즘), 이분검색

코드

      function solution(c, stable) {
        let answer;

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

        let lt = 1,
          rt = stable.slice(-1)[0];

        while (lt <= rt) {
          let mid = parseInt((lt + rt) / 2);
          let ep = stable[0];
          let count = 1;

          for (let i = 1; i < stable.length; i++) {
            if (stable[i] >= ep + mid) {
              count++;
              ep = stable[i];
            }
          }

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

        return answer;
      }

풀이 방법

이 문제도 이분검색으로 풀어야하는 문제이다.

 

-lt, rt의 정의

두 말 사이의 거리는 [1, 가장 큰 마구간의 좌표]이다. 배열에서 가장 작은 값이 100이어도 다음 숫자는 101부터 올 수 있기 때문에 두 말 사이의 최소값은 1이다. 따라서 lt에 1, rt에 가장 큰 마구간의 좌표를 넣는다.

 

-while문

1. while문의 종료 조건은 lt <= rt로 두고 mid도 (lt + rt) / 2로 둔다.(이분 검색의 초반과 같음)

2. count는 현재 둔 말의 수이며 처음에 1로 둔다. 왜냐하면 가장 첫번째 마구간에는 무조건 말을 넣어야 하기 때문이다.

3. 여기서 mid는 두 말 사이의 최대 거리이다. 따라서 ep에는 가장 첫번째 마구간 좌표를 넣는다. 그러면 ep + mid보다 크거나 같은 마구간 좌표에 다음 말을 둘 수 있다.

4. for문은 가장 첫번째 마구간에는 무조건 말이 들어가니 1부터 시작한다. for문 안에서 현재 마구간이 ep보다 크거나 같은 좌표에 있다면 count를 1 올려주고 ep도 현재 좌표로 최신화한다.

5. for문이 끝나고 나서 count >= c이면 answer에 mid를 저장한다. 그리고 mid를 더 늘려야하기 때문에 lt = mid + 1을 한다.

count < c이면 mid를 줄여야하기 때문에 rt = mid - 1을 한다.