프로그래머스_예산

문제 :https://programmers.co.kr/learn/courses/30/lessons/43237#

코딩테스트 연습 - 예산 | 프로그래머스

먼저, 해당 풀이는 90점 짜리 풀이이다.

예제 케이스는 전부 통과하지만 효율성 테스트에서 3/5의 결과가 나온다.

for문을 통해 size 만큼 반복적으로 도는 것이 시간적으로 많이 잡아먹기에 효율성이 떨어지는 듯 하다.

 

핵심은 이분탐색을 통해 탐색한다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> budgets, int M) {
    int answer = 0, found=0;
    int idx=0,i=0;
    long long min = 1000000000;
    
    sort(budgets.begin(), budgets.end());
    reverse(budgets.begin(), budgets.end());
    
    // 가능한 지점 찾기
    for(i=0;i<budgets.size();i++){
        long long val =0;
        for(int j=0;j<budgets.size();j++){
            if(budgets[j]>budgets[i])
                val+= budgets[i];
            else
                val+=budgets[j];
        }
        if(val<M){
            idx=i;
            break;
        }
    }
    // 예외처리(다 최고 예산 분배 가능)
    if(idx==0 && i==0)
        return budgets[0];
    
    // 그 외
    int can_bud = budgets[idx], next_bud=budgets[idx-1];
    if(idx==0)
        can_bud = 1,next_bud=budgets[budgets.size()-1];
    
    while(true){
        int m = (can_bud+next_bud)/2;
        if(can_bud==m || next_bud == m) break;
        long long val =0;
        for(int j=0;j<budgets.size();j++){
            if(m < budgets[j])
                val+=m;
            else
                val+=budgets[j];
        }
        
        // 크다면
        if(val>M)
            next_bud = m;
        // 작다면
        else{
            can_bud = m;
            if(min>(M-val))
                answer = m;    
        }
    }
    return answer;
}

효율성을 향상시키고자 코드를 리뷰하다가 문제점을 발견했다.

1) 굳이 경계선을 찾지 않아도 이분 탐색만으로도 해결이 가능하다(N^2의 for문이 필요없다)

2) Sort 하지 않아도 최대값을 손쉽게 알아낼 수 있다(*max_element(v.begin(), v.end()))

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

// 다 더해보기
long long budget_check(int cut, vector<int> b){
    long long val =0;
    for(int i=0;i<b.size();i++){
        val += ((b[i]>cut)? cut : b[i]);
    }
    return val;
}

int solution(vector<int> b, int M) {
    int answer = 0;

    // 이분탐색
    int min = 0, max = *max_element(b.begin(), b.end());
    while(min<=max){
        int mid = (min+max)/2;
        long long val = 0;
        val = budget_check(mid, b);
        
        // 불가능 > max 낮추기
        if(val> M)
            max = mid-1;

        // 가능 > 비교해보기
        else{
            if(answer <= mid)
                answer = mid;
            min = mid+1;
        }
    }
    return answer;
}