섹션6. Sort - 9. 뮤직비디오(결정알고리즘)

☕️ 자주 쓰는 Arrays.stream 정리

• Arrays.stream(arr).sum() → 배열의 총합
• Arrays.stream(arr).max().getAsInt() → 배열의 최대값
• Arrays.stream(arr).min().getAsInt() → 배열의 최소값
• Arrays.stream(arr).average().getAsDouble() → 평균값 (double 리턴)
• Arrays.stream(arr).distinct().toArray() → 중복 제거한 배열 반환

📌 문제 설명

가수 조영필의 라이브 공연을 DVD로 제작하려고 합니다. 총 N개의 곡이 있으며, M개의 DVD에 곡들을 나눠 담아야 합니다. 이때 다음 조건을 지켜야 합니다:

• 곡의 순서는 바뀌면 안 됨
• 곡을 나눠서 담으면 안 됨
• 모든 DVD는 같은 크기여야 함

목표: DVD 용량(길이)을 최소로 하면서 M개의 DVD로 모든 곡을 담는 것

---

📝 입력 & 출력

입력

• 첫 줄: 곡의 개수 N (1 ≤ N ≤ 1,000), DVD 수 M (1 ≤ M ≤ N)
• 둘째 줄: 각 곡의 길이(자연수, 10,000 이하)

출력

• 최소 DVD 크기를 출력

---

🔸 예제 입력 & 출력

예제 입력

9 3
1 2 3 4 5 6 7 8 9

 

예제 출력

17

 

설명: DVD 크기가 17일 경우, 아래처럼 담을 수 있습니다.

• (1 2 3 4 5)
• (6 7)
• (8 9)

---

💡 해결 방법

• 결정 알고리즘(Binary Search) 사용
• 가능한 DVD 용량의 최소값을 이분 탐색으로 찾아감

핵심 아이디어

• 가능한 최소 DVD 크기: 가장 긴 곡
• 가능한 최대 DVD 크기: 모든 곡의 합
• 해당 DVD 용량(mid)으로 모든 곡을 나눌 수 있는지 체크 (count 함수)

---

💻 코드 구현 (Java)

package partSort;

import java.util.*;

public class Problem9 {
	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) {
		Problem9 T = new Problem9();
		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.print(T.solution(n, m, arr));
		kb.close();
	}
}

---

📖 코드 설명

1️⃣ count 함수

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

• 주어진 DVD 용량(capacity)으로 몇 개의 DVD가 필요한지 계산

---

2️⃣ 이분 탐색 (Binary Search)

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

• DVD 용량을 이분 탐색하면서 최소 가능한 크기를 찾아감

---

⏳ 시간 복잡도 분석

• 이분 탐색: O(log(rt - lt))
• count 함수 (매번 탐색 시): O(N)
• 전체 복잡도: O(N * log(rt - lt))

 

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런