[인프런 섹션7] 뮤직비디오 (Javascript)

👩🏻‍💻문제링크

[인프런 섹션7] 뮤직비디오 (Javascript)
유료 강의인 관계로 문제 설명은 생략합니다.

✍️Idea Sketch

2021-06-27

1. 문제 이해

• 순서 그대로 유지
• DVD 용량 최소화

2. DVD 개수와 상관없이 DVD가 꼭 담아야할 용량

• 최소용량 : 9
• 최대용량 : 1+2+…+9 = 45

3. 이분검색 구현

• left = 9, right = 45
• while (left <= right)
• left = mid+1; right = mid-1;

4. DVD용량이 mid일 때, DVD 몇 개가 필요한지 확인

function count (mid, arr) {
  let cnt = 1;
  let sum = 0;
 
  for (let i=arr.length-1; i>=0; i--) {
    sum += arr[i];
    if (sum > mid) {
      cnt++;
      sum = arr[i]
    }
  }
  return cnt;
}

✍️소스코드

2021-06-27

function count (mid, arr) {
  let cnt = 1;
  let sum = 0;
 
  for (let i=arr.length-1; i>=0; i--) {
    sum += arr[i];
    if (sum > mid) {
      cnt++;
      sum = arr[i]
    }
  }
  return cnt;
}
 
function solution(m, arr) {
  let left = arr[arr.length - 1], right = 0;
  for (let x of arr) right += x;  
  arr.sort((a, b) => a-b);
 
  while (left <= right) {
    let mid = Math.floor((right + left)/ 2);
    let cnt = count(mid, arr);
 
    if (cnt === m) return mid;
    else if (cnt < m) right = mid-1;  // 저장용랑이 크다
    else if (cnt > m) left = mid+1;  // 저장용량이 부족하다
  }
}

✍️놓친 것 2가지

1. arr.sort()할 필요 없다

• let left = Math.max(…arr);
• let right = arr.reduce((a, b) => a+b, 0);

2. if (count(mid, arr) === m) return mid; 에서 생기는 문제

• mid-1, mid-2, … 의 용량으로도 문제조건을 만족할 수 있다.
• 따라서 if (count(mid, arr) === m) 일 때 무조건 연산을 종료하면 안된다.

if (count(mid, arr) <= m) right = mid-1;