📌강의 정리
이분 탐색의 범위는 주어진 배열이 아닌 DVD의 용량크기이다.
따라서 최소 9에서부터 최대 45까지에서 음악이 나누어지는게 가능할때 mid값을 구해야한다.
처음 mid는 lt + rt / 2 이고 그걸 전체 노래목록에서 하나씩 더하면서 mid보다 커질때 cnt를 ++하고
sum에는 x를 넣어주어 sum을 초기화하고 다시 더해간다.
그러면 mid 값에서의 dvd개수가 나오고 그게 주어진 음반보다 작으면 우선 answer에 할당시켜준뒤
다시 이분탐색을 해서
- count해준게 주어진 dvd개수보다 작거나 같은지
- 작거나 같다면 answer를 그 mid값으로 업데이트한다.
- 이후 rt값을 mid -1로 바꿔준다.
- 그렇지 않다면 lt값을 mid + 1로 바꿔준다.
해주고 lt가 rt보다 커지면 반복을 멈추고 이분탐색으로 효율적으로 모든 dvd 길이의 경우의수를 봤기에 answer를 반환한다.
📌느낀점
이제까지의 문제중 가장 어려우면서 제일 심오하고 알고리즘의 본질(?)에 근접한 문제이지 않았나 싶다.
강의를 보면서 이게 이렇게 풀릴 수가 있구나 생각이 들었고
왜 나는 이분탐색을 계속 주어진 음반배열에만 사용할 생각을 하고
사고를 더 확장해서 dvd 길이에는 사용할 생각을 못했는지 그게 아쉽다.
이번 문제는 진짜 틈틈이 계속 리마인드하며 잘 기억해 놔야 겠다.
정말 좋은문제이고 중요한 문제이다.
//나의 코드
<html>
<head>
<meta charset="UTF-8" />
<title>출력결과</title>
</head>
<body>
<script>
function count(songs, capacity) {
let cnt = 1,
sum = 0;
return cnt;
}
function solution(m, songs) {
let answer;
const result = songs.reduce((sum, curr) => sum + curr);
const avarage = result / m;
let lt = 0,
sum = 0;
let rt = songs.length;
for (let x of songs) {
let mid = (lt + rt) / 2;
for (let i = lt; i < mid; i++) {
sum += songs[i];
}
if (sum > avarage) rt = mid;
else if (sum < avarage) lt = mid;
else lt = i;
}
console.log(avarage);
return answer;
}
//우선 노래들을 전부 더한 다음에 m으로 나누어
//평균값을 구한다.
//이후 이분탐색을 이용해서 평균에 최대한 가깝게들 합을 구하고
//그 합들중 가장 큰값을 출력한다.
let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
console.log(solution(3, arr));
</script>
</body>
</html>
//강사님 코드
<html>
<head>
<meta charset="UTF-8" />
<title>출력결과</title>
</head>
<body>
<script>
function count(songs, capacity) {
let cnt = 1,
sum = 0;
for (let x of songs) {
if (sum + x > capacity) {
cnt++;
sum = x;
} else sum += x;
}
return cnt;
}
function solution(m, songs) {
let answer;
let lt = Math.max(...songs);
let rt = songs.reduce((a, b) => a + b, 0);
while (lt <= rt) {
let mid = parseInt((lt + rt) / 2);
if (count(songs, mid) <= m) {
answer = mid;
rt = mid - 1;
} else {
lt = mid + 1;
}
}
return answer;
}
let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
console.log(solution(3, arr));
</script>
</body>
</html>
'JS 알고리즘 문제풀이 > 섹션 7. 정렬과 그리디, 결정알고리즘' 카테고리의 다른 글
| 12.마구간 정하기(결정알고리즘) (0) | 2022.07.11 |
|---|---|
| 10.이분검색 (0) | 2022.07.08 |
| 9.결혼식 (0) | 2022.07.07 |
| 8.회의실 배정 (0) | 2022.07.06 |
| 7.좌표 정렬 (0) | 2022.07.05 |