[결정 알고리즘] 뮤직비디오

 

 

 

 

설명

 

 

 

 

 

 

풀이

 

결정 알고리즘이란 이분 검색을 이용하는 것이다. lt와 rt 사이에 반드시 답이 있다고 보장할 수 있는 문제에만 적용이 가능하다. 답으로서 가능한지 범위를 좁혀 나가면서 최종적으로 답을 결정한다. 좋은 답을 향해 좁혀 나가는 알고리즘이다.

 

 

solution 함수 로직은 다음과 같다.

• 정답이 될 변수 answer를 0으로 초기화 한다.
• lt는 배열의 최댓값이고, rt는 배열의 합이다.
  • 배열의 최댓값은 Arrays.stream(arr).max().getAsInt() 로 구한다.
  • 배열의 합은 Arrays.stream(arr).sum() 으로 구한다.
• 이분 탐색을 수행한다. lt가 rt보다 작거나 같을 때 반복한다. while (lt <= rt)
  • 여기서 mid 변수는 DVD 한 장의 용량을 의미한다. mid 변수는 (lt + rt) / 2, 즉 중간값이다.
  • count 함수를 호출하여 이 함수의 리턴값이 DVD 개수보다 작거나 같다면 가능한 답이다. 
    • answer는 mid가 된다.
    • rt는 mid - 1로 설정한다. 즉, 작은 부분을 이어서 탐색한다.
    • 검색 범위가 절반으로 줄어든다.
  • 그렇지 않다면
    
    • lt는 mid + 1로 설정한다. 즉, 큰 부분을 이어서 탐색한다.
    • 검색 범위가 절반으로 줄어든다.
• answer를 리턴한다.

 

 

 

count 함수는 다음과 같다.

• 매개변수로 배열(arr)과 용량(m)을 받는다.
• 리턴할 값은 DVD 장수이다.
• int형 변수 cnt는 DVD 장수를 나타내며 초기값은 1이다. 이 값이 리턴할 값이다.
• int형 변수 sum은 DVD 에 담아내는 곡들의 분수 합을 나타내며 초기값은 0이다.
• 배열을 순회하며 다음 로직을 수행한다.
  • sum + 현재 배열값이 매개변수로 전달받은 용량보다 크다면, 한 장의 용량을 넘어가는 것이다.
    • 그렇다면 새로운 장수가 필요한 것이므로 cnt를 1 증가시킨다.
    • sum은 현재 배열값으로 세팅한다.
  • 그렇지 않다면 현재 DVD에 이어서 곡을 담을 수 있으므로
    • 현재 배열값을 sum에 누적한다.
• cnt를 리턴한다.

 

 

 

 

+) stream에 대한 추가적인 내용

• stream은 reduction 함수를 제공한다. reduction 함수를 이용해서 데이터를 가공하고 정보를 얻을 수 있다.
• stream의 max는 리턴값이 Optional<Integer>이므로 getAsInt로 반드시 int를 리턴하도록 해야한다.
• stream의 sum은 리턴값이 int 이므로 별도의 작업을 해줄 필요가 없다.

 

 

 

 

코드

 

package inflearn._6_9;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * 문제 예시
 * DVD 한 장은 최소 9분이어야 함 -> 가장 긴 영상 길이가 9분
 * DVD 한 장은 최대 45분임 -> 모든 노래가 하나의 DVD에 들어갈 수도 있으니까
 * lt = 9, rt = 45
 * mid = (9 + 45) / 2 =  27 -> DVD 한 장의 용량이라고 생각해보자
 *  - 담을 수 있는지, 없는지 검증 -> 함수로 만들자
 *  - 1~6까지 1장, 7~9까지 1장 -> 총 2장으로도 가능, 2장으로 가능하면 3장으로도 가능함!
 *  - -> 담아낼 수 있음
 * answer = 27
 *
 * 더 좋은 답을 향해 감
 *  rt = mid -1
 *  mid = (9 + 26) / 2 = 17
 *  - 1~5까지 1장, 6~7까지 1장, 8~9 1장 -> 총 3장으로 가능
 *  - -> 담아낼 수 있음
 *  answer = 17
 */
public class Main {

    public static int count(int [] arr, int capacity) {

        /**
         * cnt : DVD 장수
         * sum : DVD에 담아내는 곡들의 합
         */
        int cnt = 1, sum = 0;

        for(int x : arr) { // 첫번째 장부터 담는다
            if (sum + x > capacity) { // 한 장의 용량을 넘어가면
                // 새로운 장수가 필요한 것
                cnt++;
                sum = x; // 현재 사용하고 있는 DVD 장에 몇 분이 저장되고 있는가를 저장하는 변수
            }
            else { // 한 장의 용량보다 작다면
                sum += x; // 누적
            }

        }


        return cnt;

    }

    /**
     * count 함수에서 리턴한 값이 m(DVD 수)보다 작은지 확인하는 로직 필요
     */
    public static int solution(int n, int m, int [] arr) {

        int answer = 0;

        /**
         * lt : 배열 중 가장 큰 값
         * rt : 배열을 모두 더한 값
         */
        int lt = Arrays.stream(arr).max().getAsInt();
        int rt = Arrays.stream(arr).sum();

        while (lt <= rt) {
            int mid = (lt + rt) / 2; // mid 가 DVD 한장의 용량
            if (count(arr, mid) <= m) { // m보다 같거나 작다면 가능한 답
                answer = mid;
                rt = mid -1;
            }
            else {
                lt = mid + 1;
            }
        }


        return answer;

    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken()); // 곡 개수
        int m = Integer.parseInt(st.nextToken()); // DVD 개수

        int [] arr = new int[n];

        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        bw.write(sb.append(solution(n, m, arr)).toString());
        bw.flush();

        bw.close();
        br.close();
    }
}