❓❓❓ 뮤직비디오 : 결정 알고리즘(Binary Search)

Solution 풀이

function count(songs, mid) {
  let sum = 0;
  let cnt = 1; // 틀린 부분 (cnt = 0)
  for (let x of songs) {
    sum += x;
    if (sum > mid) {
      cnt++;
      sum = x;
    }
  }
  return cnt;
}

function solution(m, songs) {
  let answer;
  let l = Math.max(...songs);
  let r = songs.reduce((sum, v) => sum + v, 0);
  while (l <= r) {
    let mid = parseInt((l + r) / 2);
    if (count(songs, mid) <= m) {
      answer = mid; // 틀린 부분 (아예 마지막에 맞은 답을 저장 안함)
      r = mid - 1;
    } else l = mid + 1;
  }
  return answer;
}

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

거의 손도 못댔다... 난이도가 갑자기 확 뛴것 같다

배운 점

• 이분 검색으로 답을 결정
• 배열의 최대값을 찾을 때에는 전개 연산자 ... 사용
• 가장 마지막 답을 answer에 저장해 두어야 함!! (안그럼 계속 갱신된다 ㅠㅠ)

느낀 점

• Binary Search로 이렇게 문제를 풀 수 있다는 것을 보고 충격을 받았다 ㅠㅠ
• 거기다 더해 Solution 눈으로 훑고 다시 코드 작성했는데도 못풀었다 ㅠㅠ