코드 리뷰 부탁드립니다
244
작성한 질문수 9
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가 나오면 이 값으로 정답을 교체해가는 방식입니다.
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





