코틀린 코딩테스트 강좌, 블루레이 만들기

문제 설명

블루레이 디스크는 대용량 데이터를 저장할 수 있는 매체로, 영화나 음악, 데이터 파일을 포함할 수 있습니다.
최근 한 기업에서 블루레이 디스크에 데이터를 효율적으로 저장하기 위한 알고리즘을 개발하고자 합니다.
이에 따라 각 블루레이 디스크는 특정한 용량을 갖고 있으며, 여러개의 파일을 이 디스크에 저장해야 합니다.
저장해야 할 데이터의 크기와 각 디스크의 최대 용량이 주어졌을 때, 최소 몇 개의 디스크가 필요한지를 구하는 문제입니다.

입력

첫 번째 줄에는 데이터 파일의 개수 N (1 ≤ N ≤ 1000)과 각 파일의 크기 S_i (1 ≤ S_i ≤ 10^6)를 포함하는 정수 배열이 주어집니다.
두 번째 줄에는 각 블루레이 디스크의 최대 용량 C (1 ≤ C ≤ 10^6)가 주어집니다.

출력

디스크의 최소 개수를 출력합니다.

예제

입력

    5
    2 4 3 6 5
    8

출력

    2

문제 접근

이 문제를 해결하기 위해서는 다음과 같은 접근 방식이 필요합니다:

  1. 각 파일의 크기를 정렬하고 가장 큰 파일부터 블루레이 디스크에 하나씩 저장합니다.
  2. 블루레이 디스크에 저장할 때 현재 디스크에 파일을 추가했을 때 용량을 초과하지 않도록 합니다.
  3. 현재 디스크에 파일을 추가하기에 용량이 부족하다면 새로운 디스크를 사용해야 합니다.
  4. 모든 파일을 저장할 때까지 이 과정을 반복하여 디스크의 총 개수를 계산합니다.

코드 구현

아래는 코틀린으로 작성한 코드입니다: 


fun minNumberOfDisks(fileSizes: List, capacity: Int): Int {
    val sortedFiles = fileSizes.sortedDescending() // 파일 크기를 내림차순으로 정렬
    var diskCount = 0
    var currentDiskUsage = 0

    for (fileSize in sortedFiles) {
        if (currentDiskUsage + fileSize > capacity) {
            diskCount++ // 새로운 디스크 추가
            currentDiskUsage = fileSize // 현재 파일로 디스크 초기화
        } else {
            currentDiskUsage += fileSize // 현재 디스크에 파일 추가
        }
    }

    // 마지막 디스크도 계산하기 위해 +1
    return diskCount + if (currentDiskUsage > 0) 1 else 0
}

fun main() {
    val fileSizes = listOf(2, 4, 3, 6, 5) // 입력 파일 크기
    val capacity = 8 // 블루레이 디스크의 최대 용량
    println(minNumberOfDisks(fileSizes, capacity)) // 결과 출력
}

코드 설명

– minNumberOfDisks 함수는 파일 크기 리스트와 디스크 용량을 입력받습니다.
– 파일 크기를 내림차순으로 정렬한 후, 각 파일을 추가할 디스크를 결정합니다.
– 현재 디스크의 사용량이 용량을 초과하면 새로운 디스크를 추가하고, 파일의 사용량을 기존 디스크의 사용량으로 초기화합니다.
– 모든 파일을 처리한 후, 총 디스크 개수를 반환합니다.
– main 함수에서 예제 입력을 통해 기능을 확인합니다.

결론

이번 문제는 효율적인 디스크 관리와 저장 공간 활용에 대한 전반적인 이해를 필요로 합니다.
모든 파일을 저장하기 위해 필요한 최소한의 디스크 수를 구하는 문제는 다양한 분야에서 응용이 가능합니다.
알고리즘 문제를 풀면서 발생하는 여러 가지 상황을 고려하고 최적화하는 과정을 통해 프로그래밍 능력을 향상시킬 수 있습니다.

추가 도전 과제

– 블루레이 디스크의 개수가 정해져 있을 때, 파일의 배치 방식을 최적화하는 방법을 연구해보세요.
– 다양한 용량의 블루레이 디스크를 다룰 수 있는 알고리즘을 구현해보세요.