inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)

11. 뮤직비디오(결정알고리즘)

코드 리뷰 부탁드립니다

244

je

작성한 질문수 9

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보다 작거나 같은 경우에 무조건 정답으로 대입해도 괜찮은 이유가 무엇인가요?

javascript 코딩-테스트

답변 1

0

김태원

안녕하세요^^

반례가 없어 보입니다.

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

continue를 사용하는 이유

0

82

2

정렬 가능 여부 판단하기

0

66

2

알고리즘 학습법 관련해서 질문드립니다.

0

86

1

코드 리뷰 부탁드립니다!

0

90

1

indexOf를 사용해서 풀어보았습니다 !!

0

69

1

저는 이런식으로 구현 해보았습니다 !!

0

65

1

12,13,14 강의 소리만 나오고 검은 화면입니다

0

101

3

반복문 최소화하고 indexOf 사용해서 풀어봤습니다

0

63

1

영상 보기 전에 직접 풀어봤습니다.

0

75

1

섹션1의 17번문제 이 풀이로 풀어도 될까요?

0

136

2

정규표현식으로 처리해도 상관없나요 ?

0

120

2

3칸씩 건너뛸 수 있을 경우

0

126

2

강의에 대해 질문있습니다.

0

136

2

Object와 Set을 이용해 풀어봤습니다.

0

117

2

이렇게 해도 되나요?

0

102

2

선생님 중복 단어나 중복관련 문제들은 set을 이용하면 좋을것 같습니다.

0

145

2

이렇게 풀어도 괜찮을까요?

0

138

1

이렇게 풀어도 괜찮을까요?

0

113

1

모든 아나그램 찾기에서 시간복잡도

0

98

1

코드리뷰 부탁드립니다.

0

130

1

for loop 탈출은 return 문으로 해도 되지 않나요?

0

133

1

투포인트알고리즘으로 풀어봤습니다.

0

142

0

코드 리뷰 부탁드립니다.

0

120

1

코드 맞게 작성한 거 아닌가여??

0

146

1