스위프트 코딩테스트 강좌, 블루레이 만들기

코딩테스트 준비에서 알고리즘 문제를 풀어내는 것은 매우 중요한 과정입니다. 본 강좌에서는 스위프트 프로그래밍 언어를 사용하여 ‘블루레이 만들기’라는 문제를 해결하는 방법을 알아보겠습니다. 이 문제는 실제 취업시험에서 자주 등장하는 문제로, 자료구조와 알고리즘을 동시에 이해할 수 있는 좋은 기회가 될 것입니다.

문제 설명

주어진 ‘블루레이 만들기’ 문제는 N개의 영화가 있으며, 각 영화의 길이는 배열 filmLengths에 주어집니다. 당신은 이 영화들을 블루레이에 담아야 하며, 각 블루레이의 최대 용량은 maxCapacity로 제한됩니다. 블루레이의 수를 최소화하며 모든 영화를 담는 방법을 찾는 문제입니다.

함수 서명은 다음과 같습니다:

func minimumBluRays(filmLengths: [Int], maxCapacity: Int) -> Int

입력 예시

let films = [90, 85, 75, 60, 120]
let maxCap = 180

출력 예시

minimumBluRays(filmLengths: films, maxCapacity: maxCap) // 결과: 3

접근 방법

이 문제를 해결하기 위해서는 두 가지 접근 방법을 고려할 수 있습니다.

그리디 알고리즘(Greedy Algorithm): 영화의 길이를 오름차순으로 정렬한 후 가장 긴 영화를 나머지 영화들과 동시에 블루레이에 담는 방법입니다. 이러한 방법으로 매번 최대한의 영화를 블루레이에 담아가는 방식입니다.
이진 탐색(Binary Search): 최대로 담을 수 있는 블루레이 수를 이진 탐색으로 결정하는 방법입니다. 가능한 최대 블루레이 수의 범위를 설정하고, mid 값을 기준으로 필요한 블루레이 수를 카운트합니다. 이 방식 역시 효율적인 해결책이 될 수 있습니다.

해결 과정

여기서는 그리디 알고리즘을 사용하여 문제를 해결하는 방법을 자세히 살펴보겠습니다.

1단계: 영화 정렬

먼저 주어진 영화 길이를 오름차순으로 정렬합니다. 이렇게 하면 가장 짧은 영화부터 차례로 블루레이에 담으면서, 가장 긴 영화와 나머지 영화를 조화를 이루게 배치하는 것이 가능합니다.

let sortedFilms = filmLengths.sorted()

2단계: 블루레이 배치 로직 구현

각 블루레이에 영화들을 담을 수 있는지 판단하는 로직을 구현합니다. 블루레이의 현재 용량을 관리하면서, 추가할 영화가 용량을 초과하지 않는다면 해당 블루레이에 담습니다. 용량을 초과한다면 새로운 블루레이를 생성합니다.


var bluRayCount = 1
var currentCapacity = 0

for film in sortedFilms {
    if currentCapacity + film <= maxCapacity {
        currentCapacity += film
    } else {
        bluRayCount += 1
        currentCapacity = film
    }
}

3단계: 전체 코드

위의 단계들을 종합하여 최종 코드를 완성합니다.


func minimumBluRays(filmLengths: [Int], maxCapacity: Int) -> Int {
    let sortedFilms = filmLengths.sorted()
    var bluRayCount = 1
    var currentCapacity = 0

    for film in sortedFilms {
        if currentCapacity + film <= maxCapacity {
            currentCapacity += film
        } else {
            bluRayCount += 1
            currentCapacity = film
        }
    }
    return bluRayCount
}

// 사용 예
let films = [90, 85, 75, 60, 120]
let maxCap = 180
print(minimumBluRays(filmLengths: films, maxCapacity: maxCap)) // 결과: 3

시간 복잡도

이 솔루션의 시간 복잡도는 O(N log N)입니다. 영화 길이를 정렬하는 데 O(N log N)이 필요하며, 그 이후의 반복에서는 O(N) 시간이 소요됩니다. 따라서 전체적으로 효율적인 해결책입니다.

결론

본 문제는 실제 코딩 테스트에서 많이 등장하는 문제이며, 그리디 알고리즘을 통해 효과적으로 해결할 수 있습니다. 문제를 이해하고 접근 방법을 잘 설정하여 연습한다면, 다양한 코딩 테스트에서 좋은 결과를 얻을 수 있을 것입니다. 스위프트 언어의 특징을 익히며 이러한 문제를 풀어내는 연습을 지속적으로 해보세요.

참고 문헌

Introduction to Algorithms, Thomas H. Cormen
Algorithms, Robert Sedgewick
Swift Programming: The Big Nerd Ranch Guide, Matthew Mathias