[C++/프로그래머스] 예산

✅ LV. 1

✏️ 솔루션

1. total은 모든 부서의 신청 예산을 sum한 값, 처음은 모든 부서의 예산을 지원할 수 있다고 가정하고 answer 값에 부서 개수를 저장
2. 각 부서의 신청 예산을 내림차순 정렬
3. total <= budget 이면 모든 부서의 예산을 지원할 수 있다고 판단
4. total > budget 이면 예산 지원에서 부서를 제외하는데 이 때마다 부서 개수 빼주기(answer--), total 값에서도 제외한 부서 예산 값 빼주기
5. 반복문을 통해 3, 4 과정 반복

✏️ 최종 코드

#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> d, int budget) {
    int answer = d.size();
    vector<int> v;
    
    int total=0;
    for(int i=0;i<d.size();i++) {
        total+=d[i];
    }
    
    sort(d.rbegin(),d.rend());  //내림차순
    
    for(int i=0;i<d.size();i++) {
        //예산보다 작거나 같을 경우
        if(total<=budget) return answer;
        //예산보다 클 경우
        if(total>budget) {
            answer--;
            total-=d[i];
        }
    }
    
    return answer;
}

✏️ 개선 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

1. 각 부서의 신청 예산 오름차순 정렬
2. 신청 예산이 작은 부서부터 지원하는 방식으로 차례로 더해갔을 때 예산을 초과하는 순간이 오면 그 시점까지 더한 부서 개수 return 하는 방식

✏️ 회고

• 개선한 코드가 더 간결하고 변수 선언을 최소화하고 연산과정도 단축할 수 있어서 효율적
• 개선 전 코드로 했을 때는 정답처리 되기는 했지만 런타임이 오래 걸려서 조마조마했음ㅠ