• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

코드 리뷰 부탁드립니다

23.03.31 01:29 작성 조회수 164

0

const solution = (m, songs) => {
  let lt = Math.max(...songs),
    rt = songs.reduce((prev, cur) => prev + cur);
  let mid = parseInt((lt + rt) / 2);
  let nowCount;
  let minMinutes = Number.MAX_SAFE_INTEGER;

  const getCount = (minutes, songs) => {
    let count = 0;
    let remainMinutes = 0;
    for (let song of songs) {
      if (remainMinutes < song) {
        count++;
        remainMinutes = minutes - song;
      } else {
        remainMinutes -= song;
      }
    }

    return count;
  };

  while (lt <= rt) {
    nowCount = getCount(mid, songs);
    console.log(mid, nowCount, minMinutes);
    if (nowCount > m) {
      lt = mid + 1;
    } else {
      rt = mid - 1;
      // if (nowCount === m) minMinutes = Math.min(minMinutes, mid);
      minMinutes = mid;
    }
    mid = parseInt((lt + rt) / 2);
  }

  return minMinutes;
};

먼저 getCount 부분을 다르게 작성해봤는데 반례가 있을지 궁금합니다.

그리고 제 원래 코드는 while문 내에서 구한 nowCount값이 m과 같을 때만 minMinutes(정답)을 minMinutes와 mid 중 더 작은 값으로 대입해줬는데, nowCount가 m보다 작거나 같은 경우에 무조건 정답으로 대입해도 괜찮은 이유가 무엇인가요?

답변 1

답변을 작성해보세요.

0

안녕하세요^^

반례가 없어 보입니다.

nowCount가 m보다 작다는 것은 mid용량을 가진 DVD로 m이하의 장수로 모든 노래를 순서를 유지하면서 저장할 수 있다는 의미입니다. 그래서 mid 용량을 일단 답으로 하고 더 좋은 답을 찾가 이분검색으로 좁혀 들어가는 것입니다. 좁혀 들어가다가 더 작은 정답이 될 수 있는 mid가 나오면 이 값으로 정답을 교체해가는 방식입니다.