[JS] 코딩 테스트 문제 : 뮤직비디오 [2진 탐색, 결정알고리즘]

문제 : 뮤직비디오(결정알고리즘)

문제 설명

지니레코드에서 가수의 라이브 동영상을 DVD로 만들어 판매하려 한다. DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지되어야 한다. 순서가 바뀌는 것을 가수가 매우 싫어한다. 즉, 1번 노래와 5번 노래를 같은 DVD에 녹화하기 위해서는 1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야 한다. 또한 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다.

지니레코드 입장에서는 이 DVD가 팔릴 것인지 확신할 수 없기 때문에 이 사업에 낭비되는 DVD를 가급적 줄이려고 한다. 고민 끝에 지니레코드는 M개의 DVD에 모든 동영상을 녹화하기로 하였다. 이 때 DVD의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 그리고 M개의 DVD는 모두 같은 크기여야 제조원가가 적게 들기 때문에 꼭 같은 크기로 해야 한다.

▣ 입력설명

첫째 줄에 자연수 N(1≤N≤1,000), M(1≤M≤N)이 주어진다. 다음 줄에는 조영필이 라이브에서
부른 순서대로 부른 곡의 길이가 분 단위로(자연수) 주어진다. 부른 곡의 길이는 10,000분을
넘지 않는다고 가정하자.

▣ 출력설명

첫 번째 줄부터 DVD의 최소 용량 크기를 출력하세요.

▣ 입력예제 1

9 3
1 2 3 4 5 6 7 8 9

▣ 출력예제 1

17

설명 : 3개의 DVD용량이 17분짜리이면 (1, 2, 3, 4, 5) (6, 7), (8, 9) 이렇게 3개의 DVD로 녹음을 할 수 있다. 17분 용량보다 작은 용량으로는 3개의 DVD에 모든 영상을 녹화할 수 없다.

내코드

// 최소 가능 DVD 용량을 1씩 증가시켜 가며 모든 곡이 알맞게 들어갈 수 있는지 여부를 판단해 값을 반환하는 방식
function solution(m, songs) {
  let totalTime = songs.reduce((p, c) => p + c, 0); // 전체 곡의 길이(분단위)
  // 전체 곡의 길이(분단위) / m 한 값에 올림한 값(가능한 최소의 DVD 용량)으로 answer 를 초기화
  let answer = Math.ceil(totalTime / m);

  // 최대 DVD 용량(totalTime - songs.length - 1) 까지 answer 를 + 1 해가며 반복
  // ※ totalTime - songs.length - 1 가 최대 DVD 용량인 이유: 곡의 길이가 자연수로 최소 길이는 1 이므로 가능한 최대의 DVD 용량에 전체 플레이 타임에 배열의길이에 -1 만큼 뺀 값이다.
  while (answer < totalTime - songs.length - 1) {
    console.log(answer);
    let count = 1; // 채워지고있는 DVD 번호이자 DVD 갯수
    let sum = 0; // count 번의 DVD 에 현재 메모리 용량

    // 전체곡 배열을 순회
    let i;
    for (i = 0; i < songs.length; i++) {
      // sum 에 songs[i] 더한 메모리용량이 answer 보다 적다면 sum 에 songs[i] 더해서 저장
      if (sum + songs[i] <= answer) sum += songs[i];
      else {
        // sum 에 현재곡 용량(songs[i]) 더한 메모리용량이 answer 를 넘어갈 경우 다음 DVD 에 등록해야하므로 count 를 1 증가
        // 이후 새로운 DVD 용량이므로 sum 을 0 으로 초기화 후 현재곡 용량(songs[i])을 등록
        sum = 0 + songs[i];
        count++;
      }
      console.log(i, sum, count);

      // m 개를 넘어가는 경우 가능한 DVD 갯수 m 을 넘어가므로 break
      if (count > m) break;
    }

    console.log(i, songs.length, count, sum);
    // 1. i === songs.length : 모든 곡을 DVD 에 등록한지 여부
    // 2. count <= m : 가능한 DVD 갯수 m 을 넘어갔는지 여부
    // 3. sum <= answer : 마지막 DVD 용량이 최소의 DVD 용량을 넘어갔는지 여부
    // 위 경우를 모두 통과한 경우라면 정상적으로 DVD 를 최소 용량(anwer) 기준으로 m 개 만큼 등록된 것으로 보고 break
    if (i === songs.length && count <= m && sum <= answer) break;

    // 현재 최소 용량(anwer) 기준에서 정상적으로 DVD 에 녹화할 수 없는 경우이므로 DVD 최소 용량을 1 증가
    answer++;
  }
  return answer;
}

풀이

1. 전체 곡의 길이를 구하고 전체 곡의 길이(분단위) / m 한 값에 내림한 값(가능한 최소의 DVD 용량)으로 answer 를 초기화
2. 최대 DVD 용량(totalTime - songs.length - 1) 까지 answer 를 + 1 해가며 반복하는 반복문안에서 DVD 번호이자 DVD 갯수를 의미할 count 변수와 현재 DVD 에 메모리 용량을 의미할 sum 을 선언
3. 이후 전체 곡 배열을 순회하면서 sum 에 songs[i](i 번째 곡 길이이자 용량)을 더한 메모리 용량이 answer 보다 적다면 sum 에 songs[i] 더해서 저장 반대로 큰 경우 다음 DVD 에 등록해야하므로 count 를 1 증가 시키고 이후 새로운 DVD 용량이므로 sum 을 0 으로 초기화 후 songs[i]을 등록
4. 배열 순회 중 count 가 m 개를 넘어가는 경우 가능한 DVD 갯수 m 을 넘어가므로 break
5. 첫 번째 반복문 안에서 모든 곡을 DVD 에 등록한지 여부(i === songs.length), 가능한 DVD 갯수 m 을 넘어갔는지 여부(count <= m), 마지막 DVD 용량이 최소의 DVD 용량을 넘어갔는지 여부(sum <= answer)를 만족할 경우 정상적으로 DVD 를 최소 용량(anwer) 기준으로 m 개 만큼 등록된 것으로 보고 break 하여 반복문을 나가 현재 answer 값을 반환

리뷰

곡의 길이가 자연수이며 10000 을 넘지 않으므로 극단적으로 [10,10,10, 10000] 이런 곡 배열이 들어오고 m 이 2 인 경우 위 코드 기준으로 anwer 는 전체 배열의 합 / m 즉 10030 / 2 인 5015 부터 시작해 1씩 증가시켜 결국 anwer 가 10000 이 되어 마지막 곡을 받아 메모리에 저장 할 수 있는 상태가 될 것이므로 효율적이지 못한 부분이 존재한다.

보완할 수 있는 부분

// 기존코드
let answer = Math.ceil(totalTime / m);

// 보완코드
let avg = Math.ceil(totalTime / m)
let maxSong = Math.Max(songs)
let answer = avg  < maxSong  ? maxSong :  avg 

위 코드 리뷰에서도 적은 것 처럼 기존 방식에서 곡 길이가 크게 차이나서 생기는 소요를 줄이기 위해 기존의 전체값을 m 으로 나눠 최소 가능 DVD 용량을 정했던 방식에 곡 중 가장 큰 용량을 가지는 곡(maxSong )과 비교해서 평균값 보다 큰 용량을 가진 곡이 존재 할 시 answer 를 maxSong 으로 초기화해서 어느 정도 대비하는 방식으로 보완가능해 보임

※ 결국 곡 길이 간의 간극에 따른 불필요한 반복과정을 완벽히 보완했다고 볼 수는 없음

다른 해결 방법

// 답안지 방식: 2진 탐색 결정 알고리즘
// 입력된 DVD 용량(capacity)을 기준으로 곡을 등록한 후 사용된 DVD 갯수 반환하는 함수
function count(songs, capacity) {
  // cnt: DVD 갯수 sum: 현재 DVD 용량
  let cnt = 1,
    sum = 0;

  // 전체곡 배열을 순회
  for (let x of songs) {
    // 입력된 DVD 용량을 넘어가면 cnt 를 1 증가하고 sum 을 x 로 초기화
    if (sum + x > capacity) {
      cnt++;
      sum = x;
    } else sum += x; // 입력된 DVD 용량을 넘어가지 않는다면 sum 에 x 를 더함
  }
  return cnt;
}

function solution(m, songs) {
  let answer;
  // 가능한 DVD 용량의 최소 기준값을 의미하며 곡의 최대 길이로 초기화
  let lt = Math.max(...songs);
  // 가능한 DVD 용량의 최대 기준값을 최대 DVD 용량으로 초기화
  // 최대 DVD 용량은 곡의 길이가 자연수로 최소 길이는 1 이므로 가능한 최대의 DVD 용량에 전체 플레이 타임에 배열의길이에 -1 만큼을 뺀 값이다.
  let rt = songs.reduce((a, b) => a + b, 0) - songs.length - 1;

  // lt 값이 rt 값 보다 작아질 때까지 즉 2진 탐색이 마무리 된 경우
  while (lt <= rt) {
    // 가능한 DVD 용량의 중앙 값
    let mid = parseInt((lt + rt) / 2); // let mid = Math.floor((lt + rt) / 2);
    console.log(`# 중앙값: ${mid}  lt: ${lt}  rt: ${rt}`);
    // count 함수를 통해 중앙값을 기준으로 사용된 DVD 갯수를 반환해 대소 여부 판단
    // m 보다 작거나 같다면 용량이 부족하지 않고 정답에 해당할 수 있지만 DVD 용량을 더 줄일 수 있는 가능성이 있음으로 일단
    //  anwer 에 현재 값을 저장해 두고 mid 보다 작은 DVD 용량으로 시도하기위해 rt 값을 mid - 1 로 저장
    if (count(songs, mid) <= m) {
      answer = mid;
      rt = mid - 1;
    }
    // m 보다 크다면 사용된 DVD 갯수를 줄이기 위해 mid 보다 큰 DVD 용량이 필요하므로 lt 값을 mid + 1 로 저장
    else lt = mid + 1;
  }
  return answer;
}

풀이

1. 가능한 DVD 용량의 최소 기준값을 의미하는 변수 lt 선언 후 곡의 최대 길이로 초기화, 가능한 DVD 용량의 최대 기준값을 의미하는 변수 rt 선언 최대 DVD 용량(최대 DVD 용량은 곡의 길이가 자연수로 최소 길이는 1 이므로 가능한 최대의 DVD 용량에 전체 플레이 타임에 배열의 길이에 -1 만큼을 뺀 값)으로 초기화
2. lt 값이 rt 값 보다 작아질 때까지 즉 2진 탐색이 마무리 될 때 까지 반복하는 반복문 안에서 가능한 DVD 용량의 중앙 값 mid 를 선언
3. 입력된 DVD 용량(capacity)을 기준으로 곡을 등록한 후 사용된 DVD 갯수 반환하는 함수 count 선언해두고 반복문안에서 count 함수를 통해 중앙값을 기준으로 사용된 DVD 갯수를 반환해 대소 여부 판단
4. m 보다 작거나 같다면 정답에 현재 값을 임시 저장해두고 mid 보다 작은 DVD 용량을 판단해보기 위해 rt 값을 mid - 1 로 저장, m 보다 크다면 사용된 DVD 갯수를 줄이기 위해 mid 보다 큰 DVD 용량이 필요하므로 lt 값을 mid + 1 로 저장
5. 반복문이 종료되고 최종적으로 남은 anwer 값을 반환

---

참고

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/dashboard