HackerRank Mark and Toys

2021-06-22

hackerrank

1. 문제

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.

1.1. Example

The budget is units of currency. He can buy items that cost for , or for units. The maximum is items.

1.2. 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

1.3. 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 space-separated integers

1.4. Constraints

1 <= n <= 10^5
1 <= k <= 10^9
1 <= prices[i] <= 10^9

A toy can’t be bought multiple times.

1.5. Sample Input

7 50
1 12 5 111 200 1000 10

1.6. Sample Output

1.7. Explanation

He can buy only toys at most. These toys have the following prices: .

1.1. 컴퓨팅적 사고

이번 문제는 주어진 예산을 가지고 만들 수 있는 모든 경우의 수 리스트중에서 리스트의 가장 큰 맥시멈 사이즈를 구하는 문제였습니다.

단순히 이중 포문을 통하여 각각의 모든 경우를 구해주었고, 모든 경우의 값을 더해나가면서 k(budget)의 값을 초과한다는것은 예산으로 아이템을 살 수 없는 경우이기 때문에 해당되는 경우의수에서 종료를 시켜주었습니다.
각각의 경우의 수, 즉 아이템의 횟수를 매번 체크하여 k의 범위에 있을때 까지만 증가를 시켜주었습니다. 그리고 아이템의 횟수에 대한 값의 최댓값을 매번 구해주었습니다.

이때 주의 할점은 모든 값을 정렬을 시켜준후 경우의 수를 구해주게 되면 Worst Case O(N^2)의 경우를 모두 확인해보지 않아도 되기때문에 시간복잡도 성능이 용이할 것이라 판단이 됩니다.

Time Complexity

Worst Case : O(N^2)

1.2. 소스코드

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'maximumToys' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts following parameters:
     *  1. INTEGER_ARRAY prices
     *  2. INTEGER k
     */

    public static int maximumToys(List<Integer> prices, int k) {
    // Write your code here
    
        int answer = 0;
        Collections.sort(prices);
        
        for(int i=0; i<prices.size(); i++){
            int sum = prices.get(i);
            int cnt = 0;
            boolean isCheck = false;
            for(int j=i+1; j<prices.size(); j++){
                if(sum > k){
                    break;
                }else {
                    sum += prices.get(j);
                    cnt++;
                }
            }
            answer = Math.max(answer, cnt);    
        }
        return answer;
    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

        int n = Integer.parseInt(firstMultipleInput[0]);

        int k = Integer.parseInt(firstMultipleInput[1]);

        List<Integer> prices = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
            .map(Integer::parseInt)
            .collect(toList());

        int result = Result.maximumToys(prices, k);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Algorithmhackerrank