[인프런 코딩테스트] 뮤직비디오, 결정 알고리즘 (feat. 이분탐색 응용, javascript)

1. 문제

지니레코드에서는 불세출의 가수 조영필의 라이브 동영상을 DVD로 만들어 판매하려 한다. DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지되어야 한다. 순서가 바뀌는 것을 우리의 가수 조영필 씨가 매우 싫어한다. 즉, 1번 노래와 5번 노래를 같은 DVD에 녹화하기 위해서는 1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야 한다. 또한 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안 된다.

지니레코드 입장에서는 이 DVD가 팔릴 것인지 확신할 수 없기 때문에 이 사업에 낭비되는 DVD를 가급적 줄이려고 한다. 고민 끝에 지니레코드는 M개의 DVD에 모든 동영상을 녹화하기로 하였다. 이때 DVD의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 그리고 M개의 DVD는 모두 같은 크기여야 제조원가가 적게 들기 때문에 꼭 같은 크기로 해야 한다.

 

첫째 줄에 자연수 N(1≤N≤1,000), M(1≤M≤N)이 주어진다. 다음 줄에는 조영필이 라이브에서 부른 순서대로 부른 곡의 길이가 분 단위로(자연수) 주어진다. 부른 곡의 길이는 10,000분을 넘지 않는다고 가정하자.

 

첫 번째 줄부터 DVD의 최소 용량 크기를 출력하세요.

 

 

2. 풀이

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));

 

위 문제는 이분탐색을 응용하여 풀면 된다.

 

우선 문제 해석부터 해보면, N개의 노래를 넣을 수 있는 M개의 DVD 최소 용량을 구해야 한다.

이때 DVD의 용량은 모두 같아야 하며, N개의 노래 크기는 모두 다르다.

그리고 노래의 순서는 주어진 대로 유지해야 한다.

 

만일, N이 5 [1, 3, 5, 2, 4]이고, M이 3이라고 해보자.

3개의 dvd에 5개의 노래를 넣으려고 할 때, 1개의 dvd가 가져야 하는 최소 용량을 구하면 된다.

 

이제 풀이를 하나하나 분석해 보자.

 

 

let lt = Math.max(...songs);
let rt = songs.reduce((a, b) => a + b, 0);

 

우선 이분탐색의 범위부터 지정해 보자.

우리가 구해야 하는 것은 dvd의 용량이기 때문에 범위는 dvd의 최소용량 ~ 최대용량이 된다.

 

lt에는 dvd 최소 용량을 넣어줘야 하기 때문에 songs 배열에서 가장 큰 값을 넣어준다.

하나의 dvd에는 최소 하나의 노래는 들어가야 하기 때문에, 용량이 가장 큰 노래가 lt 값이 된다.

 

rt에는 최대 용량을 넣어줘야 하기 때문에 songs 배열을 모두 더한 값을 넣어준다.

모든 노래가 dvd에 들어가야 하기 때문에 최대 용량은 모든 노래를 합한 값이 된다. 

 

 

while (lt <= rt) {
   let mid = parseInt((lt + rt) / 2);
   ....
}

 

다음으로 while문을 통해서 가장 작은 용량의 값을 찾을 때까지 반복해 준다.

이분탐색에서 늘 그랬듯이 mid의 값은 (lt+rt)/2가 된다. 

 

 

if (count(songs, mid) <= m) {
    answer = mid;
    rt = mid - 1;
} else lt = mid + 1

 

우선, count 함수를 통해 dvd의 용량이 mid일 때 몇 개의 dvd가 사용되는지 받아온다.

 

그 개수가 m보다 작거나 같으면, 해당 용량으로 노래를 모두 넣을 수 있다는 의미이기 때문에 answer에 mid를 넣어준다.

그리고 이보다 더 작은 용량으로도 가능한지 체크하기 위해 rt 값을 mid -1로 변경해 준다.

 

만일, 개수가 m보다 크다면 이보다 큰 용량의 dvd가 필요하기 때문에 lt를 mid+1로 수정해 준다. 

 

 

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;
}

 

count 함수에선 dvd의 용량이 mid일 때, 모든 노래를 m개의 dvd에 넣을 수 있는지 리턴해줘야 한다.

따라서 몇 개의 노래가 들어갔는지 세기 위해 cnt 변수를 만들어주고,

하나의 dvd에 들어간 노래의 합(용량)을 알기 위해 sum 변수를 만들어준다.

 

for of를 이용해 sum에 노래를 하나씩 넣어준다.

이때 sum+x의 값이 mid보다 크다면, 한 개의 dvd 용량이 차 다음 dvd가 필요하다는 의미이다.

따라서 cnt를 ++해주고 sum의 값을 현재 노래의 용량으로 수정해준다.

 

sum+x의 값이 mid보다 크지 않다면, 계속해서 노래가 들어갈 수 있다는 의미이므로 sum에 x를 더해준다.

 

 

 

* reduce

arr.reduce(callback[, initialValue])

 

배열의 각 요소에 대해 주어진 reducer 함수(callback Fun)를 실행하고, 하나의 결괏값을 반환한다.

이때 반환되는 배열에는 각 요소에 reducer함수가 실행된 값이 누적된다.

 

reducer함수를 처음 호출하면서, initalValue값이 없다면 인덱스 1부터 시작해 reducer 함수를 실행하고, 0번째 인덱스는 건너뛴다.

만일 initalValue값이 있다면, 0번째 인덱스부터 시작한다.

 

ex)

const arr = [1, 2, 3, 4];
const sum = arr.reduce((accumulator, currentValue) => accumulator + currentValue, 0);

 

콜백함수에서 매개변수로 받는 accumulator에는 콜백함수가 실행되고 누적된 값이,

currentValue에는 현재 값이 들어온다.

 

따라서 sum에는 arr 배열의 모든 요소를 합한 값인 10이 들어간다. 

 

 

---

진짜 결정알고리즘,,,, 그래도 처음 봤을때보다 쪼오오오끔 더 이해하기 쉬웠다ㅠ 

푸는 김에 reduce에 대해서도 다시 공부했다! 오랜만에 쓰니까 넘 헷갈리더라,,