[인프런 섹션7] 마구간 정하기 (Javascript)

👩🏻‍💻문제링크

[인프런 섹션7] 마구간 정하기 (Javascript)
유료 강의인 관계로 문제 설명은 생략합니다.

✍️Idea Sketch

2021-06-28

1. 인접한 말 사이의 거리가 최대가 되도록, 가장 가까운 두 말의 최대거리

• 3마리 말을 배치
• 1, 4, 9로 배치할 경우 인접한 말 사이의 거리가 최대
• 가장 가까운 두 말의 최대거리는 4-1 = 3

2. 두 말의 최대거리를 구해야 하므로

• 두 말 사이의 모든 종류의 거리정보를 바탕으로, 이분검색
• left, right는 보다 단순하게 구현
• 두 말 사이의 최소거리를 mid라 했을 때, 마구간에 넣을 수 있는 말은 총 몇마리인지 확인

let left = Math.min(...arr), right = Math.max(...arr);

while (left <= right) {
  let mid = Math.floor((left + right) / 2);
  let cnt = count(arr, target);

  if (cnt === mid) return mid;
  else if (cnt < mid) right = mid-1; // 2마리밖에 못넣음, 그 말은 최소거리가 정답보다 크다는 말, 최소거리를 줄여야 함
  else if (cnt > mid) left = mid+1;
}

3. if (cnt === mid) 인 경우 무조건 return 하면 안된다.

• mid-1, mid-2, … 도 문제조건을 만족할 수 있다.

if (cnt <= mid) {
  res = mid;
  right = mid-1; 
}
else if (cnt > mid) left = mid+1;

4. count(arr, mid) 구현

• 말 사이의 최소거리가 mid일 때, 마구간에 넣을 수 있는 말이 몇마리인지 return
• 초기값 cnt = 1, index = arr[0];
• arr[i]가 index + mid보다 크거나 같으면 cnt++, index = arr[i]

function count(arr, mid) {
  let cnt = 1, index = arr[0];

  for (let i=1; i<arr.length; i++) {
    if (arr[i] >= index + mid) {
      cnt++;
      index = arr[i];
    }
  }

  return cnt;
}

✍️소스코드

2021-06-28

function count(arr, mid) {
  let cnt = 1, index = arr[0];

  for (let i=1; i<arr.length; i++) {
    if (arr[i] >= index + mid) {
      cnt++;
      index = arr[i];
    }
  }

  return cnt;
}

function solution(arr, target) {
  let res = 0;
  arr.sort((a, b) => a-b);
  let left = arr[0], right = arr[arr.length-1];
  // 정렬이 필요없다면 let left = Math.min(...arr), right = Math.max(...arr);

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    let cnt = count(arr, target);

    if (cnt <= mid) {
      res = mid;
      right = mid-1; 
    }
    else if (cnt > mid) left = mid+1;
  }

  return res;
}