アルゴリズム – 予算

問題説明

A社では各部署に必要なモノを支援するため、部署ごとにモノを買うのにいくら必要なのかを調べました。
でも、全体予算は決められているためすべての部署にモノを提供はできません。
それで、最大限に多い部署にモノが買えるようにしようと思っています。

モノを買うときは各部署が申請して金額全部を支援しなければなりません。
例えば1,000円を申請した部署には必ず1,000円を支援すべきであり、1,000より少なくは支援できません。

部署ごとに申請した金額が入っている配列dとbudgetがパラメータとして与えられる場合、最大いくつの部署にモノが支援できるかがreturnされるようにsolutionメソッドを作成してください。

条件

• dは部署ごとに申請した金額が入っている配列であり、長さ（全体の部署数）は1以上100以下です。
  • 例）d.length = 2の場合、部署数は2。
  • 例）d[0]= 3の場合、部署1の申請金額は3。
• dの値は部署ごとに申請した金額です。申請金額は1以上、100,000以下の自然数です。
• budgetは予算です。予算は1以上、10,000,000以下の自然数です。

入出力の例

解説

※解説は私が作成したコードなので、もっといいアルゴリズム等々ありましたら、共有してください！

import java.util.Arrays;

class Solution {
    public int solution(int[] d, int budget) {

        Arrays.sort(d); // 昇順ソート

        int cnt = 0; // 支援できる部署のカウンター用
        for (; cnt < d.length; cnt++) {
            budget -= d[cnt]; // 支援するたびに、予算から削減していく

            if (budget < 0) break;
        }

        return cnt;
    }
}

終わりに

Qiitaに記載したらコメントで他の方法も教えていただきましたので、共有します。

@saka1029

public static int solution(int[] d, int budget) {
    Arrays.sort(d);
    Arrays.parallelPrefix(d, Integer::sum);
    return (int) IntStream.of(d).takeWhile(i -> i <= budget).count();
}

@SaitoTsutomu

Pythonでやってみました。

from itertools import accumulate, takewhile
from more_itertools import ilen

def solution(d, budget):
    return ilen(takewhile(lambda v: v <= budget, accumulate(sorted(d))))

leetcodeのようにmore_itertoolsが使えない場合

def solution(d, budget):
    return len(list(takewhile(lambda v: v <= budget, accumulate(sorted(d)))))