Mark and Toys

🔗 문제 링크

https://www.hackerrank.com/challenges/mark-and-toys/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=sorting

❔ 문제 설명

Mark and Jane are very happy after having their first child. Their son loves toys, so Mark wants to buy some. There are a number of different toys lying in front of him, tagged with their prices. Mark has only a certain amount to spend, and he wants to maximize the number of toys he buys with this money. Given a list of toy prices and an amount to spend, determine the maximum number of gifts he can buy.

Note Each toy can be purchased only once.

Example

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

The budget is 7 units of currency. He can buy items that cost [1,2,3] for 6, or [3,4] for 7 units. The maximum is 3 items.

Function Description

Complete the function maximumToys in the editor below.

maximumToys has the following parameter(s):

• int prices[n]: the toy prices

• int k: Mark's budget

Returns

• int: the maximum number of toys

Input Format

The first line contains two integers, and , the number of priced toys and the amount Mark has to spend.
The next line contains n space-separated integers prices[i]

⚠️ 제한사항

• $1 ≤ n ≤ 10^5$

• $1 ≤ k ≤ 10^9$

• $1 ≤ prices[i] ≤ 10^9$

• A toy can't be bought multiple times.

---

💡 풀이 (언어 : Java)

쉬운 문제이다. 오름차순으로 값을 정렬해서 하나씩 뽑아서 k에서 차감해서 k가 장난감 가격보다 작을 때까지 계속 반복하면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	private static int maximumToys(int n, int k, int[] arr) {
		int count = 0;
		Arrays.sort(arr);
		for (int price : arr) {
			if (k >= price) {
				k -= price;
				count++;
			} else {
				return count;
			}
		}
		return count;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		System.out.println(maximumToys(n, k, arr));
	}
}