[프로그래머스] #135 예산 (Swift)

programmers.co.kr/learn/courses/30/lessons/12982

코딩테스트 연습 - 예산

1. 적용 알고리즘과 문제 설명

그리디 알고리즘을 적용하는 문제이다.

그리디 알고리즘은 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 

대표적인 문제로 knapsack 문제가 있는데, 이 문제는 0-1 knapsack 문제와 유사하지만

가방 속 아이템들의(여기서는 각 부서)가치가 아닌 아이템의 갯수만 많으면 되기 때문에

0-1 knapsack에 빗대어 표현하면 가벼운 아이템을 많이 담으면 최적해를 구할 수 있는 문제이다.

 

즉, 당장 예산이 가장 적은 부서부터 지원하여, 예산이 허용하는 만큼 가장 많은 부서를 지원하면 최적해를 구할 수 있다.

 

2. 코드에 대한 설명

소스코드

import Foundation

func solution(_ d:[Int], _ budget:Int) -> Int {
    var sumOfCost: Int = 0
    var deptCnt: Int = 0
    let costs = d.sorted()
    
    for cost in costs {
        let preSumOfCost: Int = sumOfCost + cost
        if preSumOfCost <= budget {
            sumOfCost = preSumOfCost
            deptCnt += 1
        } 
        else { break }
    }
    
    return deptCnt
}

첫번째로 풀이했을 때는

우선 각 부서의 희망금액을 담은 배열(d)을 오름차순으로 정렬한 후

모든 부서의 희망 금액을 순회하며 예산(budget)을 초과하지 않을 때까지 지원하는 방식으로 풀이했다.

 

3. 개선한 코드에 대한 설명

소스코드

import Foundation

func solution(_ d:[Int], _ budget:Int) -> Int {
    var varBudget: Int = budget
    var deptCnt: Int = 0
    var costs: [Int] = d.sorted()
    
    while deptCnt < d.count && varBudget - costs[deptCnt] >= 0 {
        varBudget -= costs[deptCnt]
        deptCnt += 1
    }
    
    return deptCnt
}

2.의 방식으로 풀이하면, sumOfCost라는 변수에 지원할 수 있는 금액을 계속 더해가며 사용해야 한다는 점에서 비효율적이다.

이는 각 부서를 순회하며 예산에서 지원할 금액을 빼가며, 예산이 0보다 작거나 같아지면 순회를 종료하는 것으로 구현할 수 있다.

while문을 이용하여 각 부서를 참조할 인덱스 변수를 사용해야하지만,

결과값인 부서의 갯수를 담은 변수를 이 인덱스 용도로 사용할 수 있기 때문에 추가적인 변수 할당은 없다. (읽기에 조금 불편해졌을뿐)

 

4. 시간 복잡도, 공간 복잡도 계산

시간 복잡도

배열 정렬에 사용한 Swift 표준 라이브러리 배열 정렬 인스턴스 메서드 sorted()의 시간 복잡도가 O(n logn) 이고,

최악의 경우 모든 부서를 지원할 수 있는 충분한 예산이 있을때

while문을 부서의 수 만큼 즉, n만큼 반복하기 때문에 O(n)이다. 이때 n은 배열 d의 크기이다.

따라서 O(nlogn + n) = O(nlog10n) 

 

공간 복잡도

두 풀이방식 모두 입력받는 d배열 외에 추가적으로 필요한 변수는 n값에 의해 선형적으로 증가하지 않기 때문에

n + 상수 => O(n) 이다.

 

5. 사용 라이브러리

Swift의 표준 라이브러리 중 Array 구조체의 인스턴스 메서드인 sorted()를 사용했다. 디폴트는 오름차순

https://developer.apple.com/documentation/swift/array/2945003-sorted

Apple Developer Documentation

 

6. 문제 풀이에 어려웠던 점

while문의 조건의 경계값 설정에 대한 고민에 시간이 걸렸다.

 

+ 변수명으로 의미를 표현하는게 읽기쉬운 코드라는 점에서 개선하기 전 코드가 더 좋은 것 같다. (그럼 개선한 코드라고 볼 수 있나?)

나아진 점이라면 변수하나를 적게 사용한다는 점, break 문을 사용하지 않아도 된다는 점, 코드가 짧아짐. 정도인듯