[boj] 2110. 공유기 설치 (node.js)

문제 요약

[boj] 2110. 공유기 설치 (node.js)

풀이

• 문제 조건을 함수로 작성한 후, 이분탐색 알고리즘의 결정 조건으로 활용하는 문제다.
• 결정 조건
  • 주어진 공유기의 설치 가능 위치가 한 집당 최대 하나이므로, 멀리 두기 위해서는 무조건 정렬 완료된 첫 집에는 설치되어야 한다.
  • 따라서 첫 번째 집부터 시작하여 마지막 설치 장소를 담은 변수를 활용하여, 마지막 설치 장소와 그 다음 설치 장소 간 거리를 주어진 거리 이상으로 할 때만 설치가 가능하다.
  • 총 설치 대수를 센 후, 문제에서 제시된 개수보다 크거나 같을 때 true를 반환한다.
• 이분 탐색에서는 결정 조건을 만족하는 마지막 값이 result 변수에 들어있도록 코딩하였다.

내 풀이

const readline = require("readline")
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
})

let cnt = 0
const input = () => stdin[cnt++]

let stdin = []
rl.on("line", function (line) {
  stdin.push(line)
}).on("close", function () {
  const [N, C] = input().split(" ").map(Number)
  let arr = []
  for (let i = 0; i < N; i++) arr.push(Number(input()))
  arr.sort((a, b) => a - b)
  console.log(binarySearch(0, 1000000000))
  process.exit()

  function binarySearch(L, R) {
    let result = arr[L]
    while (L <= R) {
      let mid = Math.trunc((L + R) / 2)
      if (isAvailable(mid)) {
        result = mid
        L = mid + 1
      } else {
        R = mid - 1
      }
    }
    return result
  }

  function isAvailable(dist) {
    let count = 1
    let last = arr[0]
    for (let i = 1; i < N; i++) {
      if (arr[i] - last < dist) continue
      last = arr[i]
      count++
    }
    return count >= C
  }
})

오늘의 느낀 점

• 이분 탐색 알고리즘에 조건을 넣을 때는 true를 만들 기준을 명확히 세우고 코딩을 시작해야 시간낭비를 줄일 수 있다.