[JavaScript/section 7] 11 - 뮤직 비디오

 📌 11 - 뮤직 비디오(결정 알고리즘)

DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지되어야 한다. 즉 1번 노래와 5번 노래를 같은 DVD에 녹화하기 위해서는 1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야 한다. 또한, 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다. M개의 DVD에 모든 동영상을 녹화하기로 했다. 이 때 DVD의 크기를 최소로 하려고 한다. 그리고 M개의 DVD는 모두 같은 크기여야 제조원가가 적게 들기 때문에 꼭 같은 크기로 해야 한다.

위 문제를 정리해보면 M개의 같은 크기를 가지고 있는 DVD에 음악을 담아야 하는데, 그 크기가 가장 최소가 되는 값을 찾는 문제이다. 특정한 상황에서 최적의 값을 구해야 하므로 이분 탐색을 이용한 파라메트릭 서치 알고리즘을 사용하면 된다.

파라메트릭 서치 알고리즘이란❓ 이분 탐색과 다르게 주어진 일련의 값들이 아니라 주어진 범위 내에서 원하는 값 또는 원하는 조건에 가장 일치하는 값을 찾아내는 알고리즘이다.

파라메트릭 서치 알고리즘의 주요 특징은 범위 내에서 조건을 만족하는 값이 있더라도 거기서 끝나는 것이 아니라 그것보다 더 좋은 최적의 답이 있는지 탐색한다는 것이다. 

 

👍 풀이 방법

최적의 답을 찾는 문제이므로 while 문은 lt가 rt를 초과하기 전까지 탐색을 계속 해야한다.

• lt는 DVD가 가질 수 있는 최소 크기이다. 한 노래를 두 개로 쪼갤 수 없기 때문에 주어진 음악들 중 제일 긴 음악이 DVD가 가질 수 있는 최소 크기가 된다.
• rt는 DVD가 가질 수 있는 최대 크기이다. songs 배열의 값들을 모두 더한 값을 저장했는데, 부른 곡의 길이가 10,000분을 넘지 않으므로 10,000으로 저장해도 된다. 최대 크기는 부정확해도 상관없다. 이분 탐색을 이용하면 한번 비교할 때마다 절반씩 탐색에서 제외되기 때문에 금방 최적의 값을 찾을 수 있다.
• count() 함수는 DVD의 크기를 인자로 받아 모든 노래를 담는데 몇 개의  DVD가 필요한지를 리턴해준다.
• 필요한 DVD의 개수가 주어진 m개 이하이면 mid(DVD의 크기)가 조건을 만족하는 값이므로 answer에 mid를 저장한다. 또한, DVD의 최소 크기를 구하고 있기 때문에 mid 이상의 값들은 탐색에서 제외된다. rt = mid - 1
• 필요한 DVD의 개수가 m개를 초과하면 mid 이하의 크기는 조건을 만족할 수 없으므로 mid 이하의 값들은 탐색에서 제외된다. lt = mid + 1

 

📝 풀이

function count(songs, capacity) {
  let dvdCnt = 1;
  let sum = 0;

  for (let x of songs) {
    if (sum + x <= capacity) {
      sum += x;
    } else {
      dvdCnt++;
      sum = x;
    }
  }

  return dvdCnt;
}

function solution(m, songs) {
  let answer;
  let lt = Math.max(...songs);
  let rt = songs.reduce((sum, song) => (sum += song));

  while (lt <= rt) {
    let mid = Math.floor((lt + rt) / 2);

    if (count(songs, mid) <= m) {
      answer = mid;
      rt = mid - 1;
    } else {
      lt = mid + 1;
    }
  }

  return answer;
}

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

 

📚 참고한 사이트

https://ywtechit.tistory.com/305?category=958175 

[ 자바스크립트(JavaScript) ] section07 - 11 - 뮤직비디오(결정 알고리즘)