[99클럽 코테 스터디 19일차 TIL] 배열

📖 오늘의 학습 키워드
배열

오늘의 회고

문제

[Maximum Number of Alloys]
https://leetcode.com/problems/maximum-number-of-alloys/description/

나의 해결

class Solution {
    public int maxNumberOfAlloys(int n, int k, int budget, List<List<Integer>> composition, List<Integer> stock, List<Integer> cost) {
        int answer = 0;
        int max = Collections.max(stock);
        for(int i = 0; i < k; i++) {
            int left = 0;
            int right = budget + max;
            while(left <= right) {
                int mid = (left + right) / 2;
                if(calculate(n, composition.get(i), stock, cost, mid, budget)) {
                    left = mid + 1;
                    answer = Math.max(answer, mid);
                } else {
                    right = mid - 1;
                }
            }
        }
        return answer;
    }
    public boolean calculate(int n, List<Integer> com, List<Integer> stock, List<Integer> cost, long mid, int budget) {
        long sum = 0;
        for(int i = 0; i < n; i++) {
            long count = mid * com.get(i);
            if(stock.get(i) < count) {
                sum += cost.get(i) * (count - stock.get(i));
            }
            if(sum > budget) {
                return false;
            }
        }
        return true;
    }
}

1. composition 배열을 돌며 k개의 기계 중 alloy 개수의 최댓값을 구할 수 있는 경우를 찾는다.
2. 각 기계에서 이진 탐색을 진행해 alloy 개수의 최댓값을 구한다.
   1) left는 0으로 초기화한다.
   2) right는 budget과 stock 배열 중 최댓값의 합으로 초기화한다.
   3) left와 right의 중간인 mid 값을 구한다.
   4) calculate 함수를 통해 mid 개의 alloy를 만들 때 필요한 금액을 구하고 budget보다 작거나 같으면 true를 반환한다. 이 경우 left를 mid에서 1 더한 값으로 갱신하고 answer 값과 mid 값을 비교해 mid가 더 크면 mid 값으로 answer를 갱신한다.
   5) 반대로 budget보다 크면 right를 mid에서 1 뺀 값으로 갱신한다.