[프로그래머스] 예산

 

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

코딩테스트 연습 - 예산

---

 

-풀이-

지원할 수 있는 최대 부서의 개수를 뽑아야한다.

최대 부서의 개수를 구하려면, 요구하는 물품의 가격이 작은 부서들을 먼저 차례대로 지원을 해주면서 예산을 뺸다면, 최대 부서의 개수가 나올것이다.

 

따라서 오름차순 정렬을 한 뒤, i번째 부서의 물품가격이 남은예산보다 더 작다면, 예산에서 빼주고 answer을 1 더해주며 d배열을 탐색하면 된다.

 

-시간복잡도-

d의 길이를 N이라고 하면, 정렬에 O(NlogN)이 걸리고, 예산을 빼주며 값을 더하는 로직은 O(N)이 걸린다. 따라서 총 시간복잡도는 O(NlogN)이 된다.

 

-코드-

//C++
#include <algorithm>
using namespace std;

int solution(vector<int> d, int budget) {
    int answer=0;
    sort(d.begin(),d.end());
    for(int i=0;i<d.size();i++){
        if(budget>=d[i]){
            budget-=d[i];
            answer++;
        }
    }
    return answer;
}

//JavaScript
function solution(d, budget) {
    var answer = 0;
    d.sort(function(a, b) {
        return a-b;
    });
    d.forEach((each)=>{
        if(budget>=each){
            budget-=each;
            answer++;
        }
    });
    return answer;
}