[이분 탐색] 마구간 정하기

🚩  마구간 정하기 문제 (이분탐색 활용)

 

📖 문제 설명 : N 개의 위치를 나타내는 마구간이 있고, C 마리의 말이 있을 때,

마구간에 말을 배치했을 때 가장 가까운 두 말의 거리의 최대를 구해라.

즉, 가장 넓은 간격으로 넣을 수 있는 최대 거리를 구하는 문제이다.

(말끼리 넓게 떨어져 있을수록 좋다)

 

💡 마구간의 좌표는 고정이 아니므로 오름차순으로 정렬한다.

제일 첫 마구간에 첫 말을 집어넣고 이분 검색을 통해 나머지 말들을 차례로 넣으면서,

넣은 말의 수와 주어진 말의 수를 비교하면서 이분 탐색 범위를 조절하여 최댓값을 추출하면 된다.

 

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

function solution(a, N) {
  let answer = 0
  let maxDistance = []
  let arrSort = [...a].sort((a, b) => a - b)

  let start = 1
  let end = arrSort[arrSort.length - 1]

  while (start <= end) {
    let mid = parseInt((start + end) / 2)
    let ep = arrSort[0] // 현재 마구간의 위치
    let cnt = 1
    arrSort.forEach((x) => {
      if (x - ep >= mid) {
        ep = x
        cnt += 1
      }
    })

    // 배치한 말의 개수가 적을 때 범위를 더 작게 탐색
    if (cnt < N) {
      end = mid - 1
    }
    // 배치한 말의 개수가 충족했을 때 범위를 더 크게 해서 최대 거리 파악
    else {
      maxDistance.push(mid)
      start = mid + 1
    }
  }

  answer = Math.max(...maxDistance)
  return answer
}

let a = [1, 2, 8, 4, 9]
console.log(solution(a, 3))

👨‍💻 코드 설명

1. 이분 탐색 범위를 지정하여 반복문을 진행한다. 마구간의 최소 범위는 1칸이고, 최대 범위는 제일 큰 마구간의 위치이다. 

 

2. 처음 마구간에 말을 넣고 cnt를 해준다. (한 마리를 배치한 상황)

 

3. 반복문을 돌면서 이전에 넣은 마구간과의 차이가 이분 탐색 mid 값 보다 큰 지 비교한다.

3-1. 클 경우 범위를 넘었기 때문에 해당 위치의 마구간에 말을 넣고 3번의 과정을 반복한다.

 

4. 3번의 과정이 끝나고 마구간에 넣은 말의 수와 주어진 말의 수를 비교하며 이분 탐색 범위를 조절한다.

4-1. 같은 경우에도 최적의 해를 위해 범위를 조절해야 한다.

 

잘못된 설명, 코드, 예외 케이스가 있다면 댓글 남겨주시면 수정하겠습니다.