문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Problem

마크와 제인은 첫 아이를 가진 후에 매우 행복하다. 그들의 아들은 장난감을 사랑해서 마크는 장난감을 사길 원한다. 그의 앞에 가격이 붙은 태그가 있는 여러 장난감들이 있다. 마크는 확실하게 소비할 돈만 가지고 있고, 그는 그 돈으로 최대한 많은 장난감을 사길 원한다. 장난감의 가격 목록과 소비할 돈이 주어질때, 그가 살 수 있는 최대 갯수를 구해라.

Example

price = [1, 2, 3, 4]
k = 7

예산은 7이다. 그는 총 비용 6인 [1, 2, 3] 또는 총 비용 7인 [3, 4]인 장난감을 살 수 있다. 최대 갯수는 3이다.

Function Description

maximumToys 함수를 완성해라.
maximumToys 함수는 아래와 같은 매개변수를 가지고 있다.

• int prices[n]: 장난감의 가격
• int k: 마크의 예산

Returns

• int: 장난감의 최대 갯수

Constraints

• 1 <= n <= 10^5
• 1 <= k <= 10^9
• 1 <= prices[i] <= 10^9
• 하나의 장난감을 여러 개 살 수 없다.

Solved

주어진 매개변수 prices를 오름차순으로 정렬한다.

prices.sort(Comparator.naturalOrder());

합을 담을 정수 sum과 장난감 갯수를 담을 정수 count를 선언하고, 각각 0을 할당한다.

int sum = 0;
int count = 0;

while문을 통해 sum이 k보다 작을 때 반복하도록 하고, 매 반복마다 sum에 가격을 더한다. 이때 더해준 값이 k보다 크면 빠져나오고 그렇지 않다면 count를 증가시킨다.

while(sum < k){
	sum += prices.get(count);

	if(sum > k){
		break;
	}

	count++;
}

count를 반환한다.

return count;

주어진 리스트 prices를 먼저 정렬해주면 쉽게 해결할 수 있는 문제다.

All Code

public static int maximumToys(List<Integer> prices, int k) {

	prices.sort(Comparator.naturalOrder());

	int sum = 0;
	int count = 0;

	while(sum < k){
		sum += prices.get(count);

		if(sum > k){
			break;
		}

		count++;
	}

	return count;
}