정확성은 다 맞는데, 효율성이 떨어진다. 효율성 2번, 3번은 도대체 어떻게 할지 모르겠다. 또한 효율성 통과 기준이 너무 높다. 19ms는 충분히 빠르다. 반드시 이분 탐색으로 풀어야 효율성 테스트를 통과하는 듯 하다. 정확성은 좀 쉬운데, 효율성 테스트가 또 마의 영역이다.
이 문제에서 이분 탐색을 어떻게 활용해야되는지 모르겠다. 너무 많이 진행되어 엎을 수 없어 보완했다.
import java.util.Arrays;
public class Bugdet {
public static void main(String[] args) {
// TODO Auto-generated method stub
Solution sol = new Solution();
int[] budgets = { 120, 110, 140, 150 };
int M = 485;
int answer = 0;
answer = sol.solution(budgets, M);
System.out.println("테스트: " + answer);
}
}
class Solution {
public int solution(int[] budgets, int M) {
//배열을 오름차순 정렬.
Arrays.sort(budgets);
/*
* for (int i = 0; i < budgets.length; i++) System.out.println(budgets[i]);
*/
int t = budgets[budgets.length - 1];
int k = 0;
long answer = 0;
int tempSum = M + 1;
while (tempSum > M) {
answer = t;
tempSum = sum(budgets, k, t);
k = Arrays.binarySearch(budgets, t);
if (k < 0)
k = -(k + 1);
k = budgets.length - k;
if (sum(budgets, k + 1, budgets[budgets.length - k - 1]) >=M)
t = budgets[budgets.length - k - 1];
else
t = t - 1;
} //while
/*
* for (int i = 0; i < budgets.length; i++) { int tempSum = sum(budgets, k, t);
* if (tempSum <= M) { answer = t; break; } else { t = t - 1; k =
* Arrays.binarySearch(budgets, t); if (k < 0) k = -(k + 1); k = budgets.length
* - k; } answer = t; }
*/
return (int)answer;
}
public int sum(int[] budgets, int k, int t) {
int tempSum = 0;
for (int i = 0; i < budgets.length - k; i++) {
tempSum = tempSum + budgets[i];
}
// for (int j = 0; j < k; j++)
// tempSum = tempSum + t;
tempSum = tempSum + k * t;
return tempSum;
}
}