[프로그래머스] 이분탐색 - 예산

*제출코드

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

long long sum(vector<int> budgets,int high){ //high: 상한선
    long long sum = 0;
    for(int i=0; i<budgets.size(); i++){
        if(budgets[i] <= high)
             sum += budgets[i];
        else 
            sum += high;
    }
    return sum;
}

int solution(vector<int> budgets, int M) {
    int answer = 0;
    sort(budgets.begin(), budgets.end()); //vector 정렬
    
    int low = 0; 
    int high = budgets[budgets.size()-1]; //상한선 범위 설정
    
    if(sum(budgets,high) <= M) //모든 요청이 배정될 수 있는 경우
        return high; 		   //최대 요청 값 return
    
    int mid;
    long long total;

    while(low <= high){
        mid = (low+high) / 2;
        total = sum(budgets,mid); //mid가 상한선일 때 요청 총액
        
        if(total > M){          //요청 총액이 예산 총액보다 크면
            high = mid - 1;     //상한선 범위 낮추기
        } else {                //요청 총액이 예산 총액보다 작거나 같을 때
            low = mid + 1;      //상한선 범위 높이기
            
            if(answer < mid){   //요청 총액이 예산 총액보다 작을 때의 최대 mid값 갱신
                answer = mid;
            }
        }
    }
    return answer; 
}

 

*review

- low, high범위 설정 후

mid값을 상한값으로 두었을 때

요청 총액이 예산 총액을 초과하는지 검사하면서

최적의 mid값을 찾는 방법

 

- 요청총액이 예산 총액 보다 작을 때의 최대 mid값을 찾는게 중요했다.

        if(total > M){          //요청 총액이 예산 총액보다 크면
            high = mid - 1;     //상한선 범위 낮추기
        } else {                //요청 총액이 예산 총액보다 작거나 같을 때
            low = mid + 1;      //상한선 범위 높이기
            
            if(answer < mid){   //요청 총액이 예산 총액보다 작을 때의 최대 mid값 갱신
                answer = mid;
            }
        }

 

- 계속 실패했던 효율성 테스트2번

1. 요청 총액을 계산할 때 sum을 int형으로 두면 오버플로우가 나므로 long타입으로 바꿔줘야한다.

2. total = sum(budgets,mid)을 변수에 저장하지 않고 매번 함수를 호출해서 비교했더니 시간 초과가 났다.