문제 :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;
}
'Archived(CSE Programming) > 알고리즘(C++)' 카테고리의 다른 글
프로그래머스_섬 연결하기 (0) | 2019.10.09 |
---|---|
프로그래머스_NQueen (0) | 2019.10.09 |
프로그래머스_네트워크 (0) | 2019.10.08 |
백준 9019_DSLR (0) | 2019.10.02 |
백준 13913_숨바꼭질 4 (0) | 2019.10.02 |