프로그래머스 예산

정확성은 다 맞는데, 효율성이 떨어진다. 효율성 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;

	}

}