[문제풀이] 06-09. 뮤직 비디오

인프런, 자바(Java) 알고리즘 문제풀이

Sorting and Searching - 0609. 뮤직 비디오

---

🗒️ 문제

---

🎈 나의 풀이

	private static int solution(int m, int[] arr) {
        int size = 0;

        for(int i : arr) size = Math.max(size, i);

        while (true) {
            int sum = 0;
            int cnt = m;

            for(int i=0; i<arr.length; i++) {
                sum += arr[i];

                if(sum > size) {
                    i--;
                    sum = 0;
                    cnt--;
                    if(cnt < 0) break;
                }
            }

            if(cnt < 0) size ++;
            else if(cnt == 0 && sum > 0) {
                size++;
            } else break;
        }

        return size;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[n];

        for(int i=0; i<n; i++) arr[i] = sc.nextInt();

        System.out.println(solution(m, arr));
    }

---

🖍️ 강의 풀이

  public int count(int[] arr, int capacity){
		int cnt=1, sum=0;
		for(int x : arr){
			if(sum+x>capacity){
				cnt++;
				sum=x;
			}
			else sum+=x;
		}
		return cnt;
	}

	public int solution(int n, int m, int[] arr){
		int answer=0;
		int lt=Arrays.stream(arr).max().getAsInt();
		int rt=Arrays.stream(arr).sum();
		while(lt<=rt){
			int mid=(lt+rt)/2;
			if(count(arr, mid)<=m){
				answer=mid;
				rt=mid-1;
			}
			else lt=mid+1;
		}
		return answer;
	}
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		int m=kb.nextInt();
		int[] arr=new int[n];
		for(int i=0; i<n; i++) arr[i]=kb.nextInt();
		System.out.println(T.solution(n, m, arr));
	}

---

💬 짚어가기

해당 문제는 결정 알고리즘을 이용하여 쉽게 해결할 수 있지만, 해당 방법을 생각하지 못하여
일반적인 반복문을 통해 풀었다. 아래 강의 풀이를 참고하길 바란다.

나의 풀이에서는 우선 가장 긴 곡의 시간을 size 변수에 저장하고, 반복문을 돌며 모든 곡이
m개의 DVD에 담길 때 까지 size의 크기를 1씩 증가시키도록 구성하였다. 반복을 최소화
하기 위해 cnt가 m을 초과하면 멈추도록 구현하였다.

해당 풀이로 테스트 케이스를 모두 통과하였지만, 이번에 다룰 알고리즘을 이용하면 실행 시간을
획기적으로 단축 시킬 수 있다.

결정 알고리즘으로 풀기

강의에서는 결정 알고리즘을 이용하여 문제를 푼다. 이 알고리즘은 사실 앞에서 풀이한 이분탐색
문제에서 소개된 이분 탐색과 동일한 알고리즘이다.

범위를 특정할 수 있고, 내가 찾는 값이 특정한 범위 내에 반드시 존재하는 경우에 결정 알고리즘을
이용하면 $O($log $n)$의 시간 복잡도만에 찾아 낼 수 있다.

풀이에서는 변수 lt와 rt 그리고 mid를 이용한다.
이는 각각 left , right , middle을줄인 것이다.

시작 값인 lt는 모든 한 개의 곡이 담길 수 있는 최소한의 짧은 길이가 되야한다. 따라서 Stream()을
이용해 배열에서의 가장 큰 값을 찾는다.

int lt=Arrays.stream(arr).max().getAsInt();
// max()의 반환형은 OptionalInt이다. 따라서 getAsInt()를 통해 Int로 얻도록 한다.

다음 마지막 값인 rt는 모든 곡을 담을 수 있는 최소한의 긴 길이가 되야한다. 마찬가지로 Stream()을
이용해 배열의 모든 값을 합한다.

int rt=Arrays.stream(arr).sum();

다음 이분 탐색을 시작한다. 핵심은 mid를 전달 받은 count() 메서드를 어떻게 구현할 것인가 이다.

count() 메서드에서는 곡의 시간이 담긴 배열을 순회하며, 각 요소의 누적 합과 전달 받은 capacity
(mid)를 비교한다. 누적합의 크기가 용량을 초과할 때 마다 count하여 리턴한다.

만약 리턴 값이 m 보다 작거나 같은 경우 answer에 mid 값을 저장한 후 계속해서 탐색을 수행하며
더 정밀한 값(DVD의 최소 용량 크기)를 찾을 수 있다.