뮤직비디오

문제

dvd의 갯수, 곡의 길이가 담긴 배열이 주어졌을 때 dvd 용량의 최소 값을 구하시오 (순서는 바꿀 수 없다)
= > 3, [1, 2, 3, 4, 5, 6, 7, 8, 9]

생각의 흐름

이분법에서는 범위를 정하는게 중요하다
반씩 범위를 줄여나가니까 범위가 조금 커도 상관은 크게 없다
범위의 start 지점 : 테이프용량의 최소 크기는 제일 긴 곡의 길이는 되어야 한다
범위의 end 지점 : 테이프 용량의 최대 길이는 곡들의 총합이다

• 더길이도 상관은 없지만 필요하지 않다

절반지점부터 테이프를 3개쓰는지 확인해준다
만약 3개 이하를 쓰면 용량을 줄인다
3개를 초과해서 쓰면 용량을 늘린다

코드로 표현하기

      function solution(tapes, songs) {
        let answer = Infinity;
        songs.sort((a, b) => a - b);
        let minimumCapacity = songs[songs.length - 1]; //테입 하나의 용량은 제일 긴 길이의 노래보다 커야한다
        let maximumCapacity = songs.reduce((pre, cur) => pre + cur, 0); //노래들의 총합보다는 작다
        //테이프 3개를 쓰고싶다
        while (minimumCapacity <= maximumCapacity) {
          let middleCapacity = Math.floor(
            (maximumCapacity + minimumCapacity) / 2
          );
          let count = 1;
          let sum = 0;
          for (let x of songs) {
            sum += x;
            if (sum >= middleCapacity) {
              count++;
              sum = sum - middleCapacity;
            }
          }
          if (count > 3) minimumCapacity = middleCapacity + 1;
          if (count <= 3) {
            maximumCapacity = middleCapacity - 1;
            answer = Math.min(answer, middleCapacity);
          }
        }
        return answer;
      }

실수했던 부분 1

            if (sum >= middleCapacity) {
              count++;
              sum = sum - middleCapacity;
            }

sum = sum - middleCapacity를 해주면 안되고
sum = x 로 해줘야 한다

• 테이프의 용량이 다 차지 않더라도 초과하게 되면 다음테이프를 꺼내고 곡을 넣어줘야 한다
  또한 sum > middleCapacity로 등호를 넣어주면 안된다

실수했던 부분 2

정렬되지 않은 배열이 주어질 수도있고 순서를 바꾸면 안되기에 오름차순으로 정렬을 할 수 없다 그래서 배열의 마지막이 제일 긴곡이 아닐 수 있다
Math.max(...songs)로 제일 긴곡을 찾아줘야 한다

중요한 부분

if (count <= 3) 여기서 꼭 부등호를 넣어줘야 하는데 3개를 쓰더라도 더 작은 용량의 테이프를 사용 할 수 있기 때문이다
그리고 Math.min 을 통해 더 작은 값을 answer에 할당해준다

이분검색을 사용해야 한다면
범위를 구하는게 제일 중요 한것같다

출처 자바스크립트 알고리즘 문제풀이