[JS] 코딩 테스트 문제 : 마구간 정하기 [2진 탐색, 결정알고리즘]

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

문제 설명

 

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

내코드

 

function solution(c, stable) {
  let answer = -1;
  let sortArr = stable.sort((a, b) => a - b);
  let lt = sortArr[0],
    rt = sortArr.at(-1);

  while (lt <= rt) {
    let cnt = Math.ceil((rt + lt) / 2); // 중앙값이자 마구간 배치거리의 기준값 변수
    let prevStable = sortArr[0]; // 다음 배치할 마구간과 비교할 이전 마굿간의 좌표값 변수
    let count = c - 1; // 배치할 말들의 현재 갯수(가장 가까운 마구간에 말을 배치한 상태로 시작해 - 1) 변수

    console.log(
      `# 마구간 배치 전 lt: ${lt}  rt: ${rt}  cnt: ${cnt}  answer: ${answer}`
    );

    // 첫번째 마구간 제외 모든 마구간 순회
    for (let i = 1; i < sortArr.length; i++) {
      // 다음 배치할 마굿간과 이전 마구간의 거리가 기준값이 되는 cnt 값과 같거나 크다면 말을 배치(count--)
      // 말을 배치했음으로 prevStable 값을 현재 마구간 위치로 변경
      if (sortArr[i] - prevStable >= cnt) {
        count--;
        prevStable = sortArr[i];
      }

      // 남은 마구간 갯수보다 말이 많이 남아있다면 조기종료
      if (sortArr.length - i + 1 < count) break;

      // 말 다 집어넣은 상황이므로 조기종료
      if (count === 0) break;
    }

    console.log(
      `# 마구간 배치 후 lt: ${lt}  rt: ${rt}  cnt: ${cnt}  count: ${count}`
    );

    // count 0 인 경우 즉 모든 말을 배치했으므로 임시로 cnt 값을 answer 에 저장
    // 다시 최대 말의 거리를 찾아야 하므로 기준값을 늘리기 위해 lt 값을 cnt + 1 로 저장
    if (count <= 0) {
      answer = cnt;
      lt = cnt + 1;
    }
    // 말을 다 집어넣지 못했음으로 기존 기준값을 줄여야 하므로 rt 값을 cnt - 1 로 줄임
    else rt = cnt - 1;
  }
  return answer;
}

풀이

 

1. 마구간 좌표 배열을 오름차순으로 정렬 후 sortArr 변수에 저장 마구간의 좌측 기준점이 될 lt 변수를 배열의 첫번째 원소로 초기화,우측 기준점이 될 rt 변수를 배열의 마지막 원소로 초기화
2. lt 가 rt 보다 작거나 같아질 때까지 반복하는 반복문 안에서 중앙값이자 마구간 배치거리의 기준값 변수로 사용될 cnt 변수를 (rt + lt) / 2 을 올림한 값으로 초기화
3. 또한 다음 배치할 마구간과 비교할 이전 마구간의 좌표값 변수 prevStable 를 sortArr 첫번째 요소로 초기화, 배치할 말들의 현재 갯수를 의미할 변수 count 를 c - 1 로 초기화 (가장 가까운 마구간에 말을 배치한 상태로 시작해 - 1 를 처리)
4. sortArr 두번째 마구간(두번째 요소)부터 순회하면서 prevStable 에서 sortArr[i] 를 뺀 값 즉 두 마구간의 거리 값이 거리 기준값 cnt 보다 크다면 말을 배치할 수 있는 것을 의미하므로 count 를 1 감소시키고 말을 배치했음으로 prevStable 값은 현재 마구간 위치(sortArr[i])로 변경
5. 만약 순회중에 남은 마구간 갯수보다 말이 많이 남아있는 경우 혹은 말 다 집어넣은 상황(count 값이 0인 경우)에 조기종료합니다.
6. 남은 count 값을 토대로 0 일 경우 모든 말을 배치했으므로 임시로 cnt 값을 answer 에 저장 후 다시 최대 말의 거리를 찾아야 하므로 기준값을 늘리기 위해 lt 값을 cnt + 1 로 저장, 반대로 말을 배치하지 못한 것을 의미(count 값이 남아있다면) 기존 기준값을 줄여야 하므로 rt 값을 cnt - 1 로 줄임
7. 위 모든 반복 과정이 종료된 후 answer 값을 반환

보완할 수 있는 부분

 

// 보완코드
function checkStable(arr, cnt, c) {
  let prevStable = arr[0];
  let count = c - 1;

  // 첫번째 마구간 제외 모든 마구간 순회
  for (let i = 1; i < arr.length; i++) {
    // 다음 배치할 마굿간과 이전 마구간의 거리가 기준값이 되는 cnt 값과 같거나 크다면 말을 배치(count--)
    // 말을 배치했음으로 prevStable 값을 현재 마구간 위치로 변경
    if (arr[i] - prevStable >= cnt) {
      count--;
      prevStable = arr[i];
    }

    // 남은 마구간 갯수보다 말이 많이 남아있다면 조기종료
    if (arr.length - i + 1 < count) break;

    // 말 다 집어넣은 상황이므로 조기종료
    if (count === 0) break;
  }
  return count;
}

function solution(c, stable) {
  let answer = -1;
  let sortArr = stable.sort((a, b) => a - b);
  let lt = sortArr[0],
    rt = sortArr.at(-1);

  while (lt <= rt) {
    let cnt = Math.ceil((rt + lt) / 2); // 중앙값이자 마구간 배치거리의 기준값 변수
    console.log(
      `# 마구간 배치 전 lt: ${lt}  rt: ${rt}  cnt: ${cnt}  answer: ${answer}`
    );

    // count 0 인 경우 즉 모든 말을 배치했으므로 임시로 cnt 값을 answer 에 저장
    // 다시 최대 말의 거리를 찾아야 하므로 기준값을 늘리기 위해 lt 값을 cnt + 1 로 저장
    if (checkStable(sortArr, cnt, c) <= 0) {
      answer = cnt;
      lt = cnt + 1;
      console.log("# 정상적으로 배치 후 거리값 저장", answer);
    }
    // 말을 다 집어넣지 못했음으로 기존 기준값을 줄여야 하므로 rt 값을 cnt - 1 로 줄임
    else rt = cnt - 1;
  }
  return answer;
}

기존의 while 문 안에 for 문안에서 마구간말 배치외 현재 말의 갯수를 처리하던 부분을 함수 checkStable 로 따로 구현하여 마구간에 배치하고 남은 말의 갯수를 반환 받아 처리하는 방식으로 변경해 가독성 증가

---

참고

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/dashboard