마구간 정하기 (결정 알고리즘)

문제

N개의 마구간이 수직선상에 있습니다. 
각 마구간은 x1, x2, x3, ......, xN의 좌표를 가지며, 
마구간간에 좌표가 중복되는 일은 없습니다. 
현수는 C마리의 말을 가지고 있는데, 
이 말들은 서로 가까이 있는 것을 좋아하지 않습니다. 
각 마구간에는 한 마리의 말만 넣을 수 있고, 
가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다. 
C마리의 말을 N개의 마구간에 배치했을 때 
가장 가까운 두 말의 거리가 최대가 되는 그 최대 값을 출력하는 프로그램을 작성하세요.
 
🔥 입력설명 
첫 줄에 자연수 N(3<=N<=200,000)과 C(2<=C<=N)이 공백을 사이에 두고 주어집니다. 
둘째 줄에 마구간의 좌표 xi(0<=xi<=1,000,000,000)가 차례로 주어집니다.

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

🔥 입력예제 1
5 3 

1 2 8 4 9

🔥 출력예제 1 
3

 

 

풀이

Q. 말이 떨어질 수 있는 최대 거리를 구하는 문제이기 때문에 이진검색을 할때 기준을

마굿간의 거리로 봐도될까요 ? 

lt  = 1 (마굿간 최소거리)

rt = 8(마굿간 최대거리)
로 잡고 해도 상관없을지 궁금합니다.

-> 맞습니다. 그렇게 해도 상관없습니다.

 

 

Tip. 결정알고리즘은 mid값이 답으로 가능하다면 그걸 답으로 해놓고 더 좋은 답을 향해서 가는 알고리즘입니다.

즉 나중에 답으로 가능한 mid값이 나온다면 기존 답보다는 더 좋은 답입니다.

예를 들어,

가장 가까운 두 말의 거리를 mid=2로 해서 검사해 2가 답으로 가능하다고 판별이 되면 일단 answer=2로 하고,

이분검색을 lt=3으로 바꾸어 2보다 작은 값들을 버려버리고 2보다 큰 값들 중에서 답을 다시 정하고

답으로 가능한 가 검사하기 때문에 만약 가능하다면 2보다는 더 좋은 답이겠죠.

우리는 거리의 최대값을 찾는 거니까요.

 

 

 

코드

  function count(stable, dist) {
    let ep = stable[0], cnt = 1; // end point는 마구간의 첫 자리값, cnt는 현재 말 마리 수
    for (let i = 1; i < stable.length; i++) { // 이미 1마리 있으니까 i = 1부터 진행
      if (stable[i] - ep >= dist) { // 지금 인덱스값인 마구간 좌표 - 현재 말 자리수가 distance 이상이면 조건 참
        cnt++  //말 1마리 추가
        ep = stable[i] // 말 위치 최신화
      }
    }
    return cnt // 말 마리 수 리턴
  }

  function solution(c, stable) {
    stable.sort((a, b) => a - b);  // 먼저 정렬을 함 [1, 2, 4, 8, 9]
    let answer, lt = 1, rt = stable[stable.length - 1]; // lt를 제일 작은 거리인 1로, rt는 마구간에서 최대거리인 9로 설정
    while (lt <= rt) {
      let mid = parseInt((lt + rt) / 2);
      if (count(stable, mid) >= c) { //만약 count함수에서 3마리 이상 나온다면
        answer = mid;   // mid 값을 우선 answer에 담는다. 최선의 mid값이 담기도록
        lt = mid + 1;   // lt값을 높여서 mid값을 높인다.
      }
      else rt = mid - 1; //만약 count함수에서 3마리 미만으로 나온다면, rt값을 줄여서 mid값을 낮춘다.
    }
    return answer;
  }
  let arr = [1, 2, 8, 4, 9];
  console.log(solution(3, arr));

 

 

 

 

출처

자바스크립트 알고리즘 문제풀이(코딩테스트 대비) - 인프런 | 강의