[이분 탐색] 뮤직비디오

🚩  뮤직비디오 문제 (이분탐색 활용)

 

📖 문제 설명 : 레코드의 수와 각 노래들의 재생 시간이 주어질 때,
레코드에 적절히 배분하였을 때, 레코드가 필요한 최소 용량을 구하는 문제이다.
즉 레코드가 3개, 노래가 순서대로 5, 6, 7, 8분짜리가 있다고 했을 때, 최소 용량은 11이 필요하다.
5분, 6분의 노래가 하나의 레코드, 7,8분짜리가 각 하나의 레코드에 들어가는 경우가 최소 용량이기 때문.

 

💡 노래 리스트 중에 제일 긴 노래를 시작 지점,  노래 리스트의 총합을 끝 지점으로 두어

이분 탐색을 진행한다. 왜냐하면 노래 리스트들의 수 만큼 레코드가 있다고 했을 때, 한 개씩 사용해도 최소 용량은 제일 큰 노래이기 때문이다. 그리고 레코드가 하나 일때는 모든 노래가 담겨있기 때문이다.

// 이분 탐색 응용
// O(nlogn)

function solution(a, M) {
  let answer = 0
  let arr = [...a]

  let start = Math.max(...arr)
  let end = arr.reduce((a, b) => a + b, 0) // 총 노래 시간
  let DVD = [] // DVD 용량

  // 제일 긴 노래 이상 ~ 총 노래 시간 사이의 조건을 이분 탐색으로 순회
  while (start <= end) {
    let mid = parseInt((start + end) / 2)
    let sum = 0
    let cnt = 1 // DVD 레코드 수
    arr.forEach((el) => {
      if (sum + el > mid) {
        DVD.push(sum)
        cnt += 1
        sum = el
      } else {
        sum += el
      }
    })
    // 마지막 노래 카운팅
    DVD.push(sum)

    // M과 DVD 개수가 같을 때
    if (M === cnt) {
      answer = Math.max(...DVD)
      break
      // M이 더 크면 용량을 더 작게 쪼개고 DVD 개수를 늘릴 수 있다.
    } else if (M > cnt) {
      end = mid - 1
    } else {
      start = mid + 1
    }
    DVD = []
  }

  return answer
}

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

👨‍💻 코드 설명

1. 이분 탐색 범위를 지정하여 반복문을 진행한다.

2. 노래의 리스트들을 더해가며 mid 조건보다 클 경우 DVD에 해당 범위까지 더 해준다.

3. 그렇게 구한 DVD 개수와 문제에서 주어진 M 개가 같은 경우는 M 개의 레코드에 정확히 다 들어갔으므로,DVD 리스트에 있는 최대 노래 수를 리턴해주면 그것이 필요로 하는 용량이다.

3-1. 조건에 부합하지 않다면 이분 탐색 범위를 재 설정한다.

 

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