[프로그래머스] 예산

<문제>

---

<전략짜기>

음.. 보통 이렇게 생긴 문제는 DP(Dynamic Programming) 이었던 것 같은데.. 😭 (잘 기억이..) 암튼 어려운 DP..

필요 예산이 적은 부서부터 순서대로 지원금을 주게 되면 제일 많은 부서의 '수'가 나오는 것은 상식적인 논리인데.. 그렇게 했을때 예외 케이스가 있을지 한참을 고민한 것 같다. (그럼 DP행....😔 😔) 근데 딱히 예외케이스가 생각이 안나서..? 일단 정렬해서 예산이 적은 순서대로 한번 지원해보기로 하고, 예산을 다쓰면 뒷 부서는 보지도 않는걸로.. 풀러 고고싱 ㅋㅋ

 

<코드>

import Foundation

func solution(_ d:[Int], _ budget:Int) -> Int {
    let array = d.sorted()
    var result = 0
    var curBudget = budget
    
    for d in array {
        if d <= curBudget {
            result += 1
            curBudget -= d
        } else {
            return result
        }
    }
    return result
}

 

<Lesson Learned>

응..?? 아니..!? DP가 아니였네!? ㅋㅋ 아니면 맞았는데 시간제한이 여유로웠거나.. 🙏 Whatever.. 하긴 근데 부서의 최대 갯수가 100개면 딱히 시간제한은 생각 안해도 됐긴 하겠다. 나는 이렇게 반복문을 돌려야 하는 문제면 가능한 반복문의 중단을 빨리 하게끔 그.. 경계점(?) 경계가 되는 순간(?)을 생각해놓고 시작한다. (이 문제의 경우는 예산이 떨어져서 더이상 지원을 못해주는 순간) 사실, 이 문제는 내가 쓰고 싶어하는 filter를 적용할 수도 있었을 것 같은데.. 그런 반복문을 중단시키고 싶은 순간을 만났을때 멈추는 걸 모르겠어서.. 💁 크게 상관없다면 아래처럼 풀어도 될 것 같다.

import Foundation

func solution(_ d:[Int], _ budget:Int) -> Int {
    var curBudget = budget

    return d.sorted().filter{
        curBudget = curBudget - $0
        return curBudget >= 0
    }.count
}

 

 

출저 : 프로그래머스 예산