[프로그래머스(Programmers)] level1 예산 자바 문제 풀이

이 문제는 level1 문제 답게 아주 간단합니다

하지만 한 번에 풀지 못했어요 ㅠㅠㅠ (한심)

진짜 아직 너무너무 부족하다는 것을 느낌 ㅠㅠ

 

처음에는 이 문제를 볼고 bfs로 풀면 되겠구나 했어요

그런데 그렇게 푸니까 모두 시간초과...

 

이거는 모든 경우를 탐색하는게 아니라 sorting이 중요한 키워드 였어요

그거를 바로 캐치하지 못한게 좀 부끄럽네요 ㅠㅠ

왜 생각을 못했을까...

아무튼 sorting을 통해서 작은 수 부터 더해가면서 budget보다 커지게 되면 break하면 되요

sorting은 Arrays.sort() 를 이용해서 간단하게 할 수 있습니다

 

https://github.com/wlgh325/Programmers_algorithm/tree/master/Level1/%EC%98%88%EC%82%B0

wlgh325/Programmers_algorithm

<프로그래머스 level1 예산 자바 코드>

import java.util.Arrays;

class Solution{
	public int solution(int[] d, int budget) {
		int num = 0;
		int sum = 0;

		Arrays.sort(d);
		
		for (int i = 0; i < d.length; i++) {
			if(sum + d[i] <= budget){
				sum += d[i];
				num++;
			}
			else
				break;
		}

		return num;
	}
}