마구간 정하기

코드

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=parseInt((lt+rt)/2);
      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));

원리

결정알고리즘

1. 정렬 및 초기값 설정
   1-1. arr의 순서를 오름차순으로 정렬한다.
   1-2. 말들의 간격이 가장 가까울 경우는 1이다. 간격을 1로 해주는 이유는 arr의 최솟값과 그다음 작은수를 찾아 빼주는게 복잡하기 때문이다.
   -> lt를 1로 지정해준다.
   1-3. 가장 간격이 경우는 arr의 최댓값 - 최솟값이다. 그러나 이역시 최댓값 최솟값 다 구하려면 복잡하기 때문에 최댓값만 구해준다.
   -> rt를 arr의 최댓값으로 지정해준다.
   1-4. 중간값인 mid의 값은 (lt+rt)/2로 지정해준다.

2. count() 생성
   2-1. 중간값인 mid를 기준으로 몇마리나 마굿간에 넣을수 있는지 판별해야한다.(count()생성)
   2-2. arr를 for문으로 돌린다. ep변수를 만들어 마지막에 말이 들어간 번호를 저장시킨다. (ep의 처음수는 무조건 arr[0]이다. 왜냐하면 가장 거리가 멀려면 무조건 첫번째 수로 말을 지정해야 하기 때문이다.)
   2-3. arr의 요소(stable[i]) - ep를 했을때 값이 mid보다 크면 말이 들어간 것이므로 cnt++를 해준다.

3. cnt에따른 mid값 재설정
   3-1. mid값을 구한후 mid값을 count()에 집어넣으면 cnt가 나온다.
   3-2. cnt가 c보다 크거나 같으면 최대거리를 좀더 늘릴 수 있다는 것이다.
   그후 answer = mid로 지정해준다. 왜냐하면 반복문을 탈출했을시에 남아있는 answer가 가장 작은 답이 될 것이기 때문이다. 또한 다음 거리를 알아보기 위해 ep에 들어간 마굿간 번호를 입력해준다.
   3-3. cnt가 c보다 작으면 최대거리의 범위를 줄여야 한다는 뜻이다. 그러므로 rt=mid-1을 해준다.
   -1을 하는 이유는 mid보다 같거나 큰수는 어차피 cnt<c를 발생시키기 때문이다.