99클럽 코테 스터디 27일차 TIL - 배열 (LeetCode 2861번)

항해99 코테 스터디 27일차 문제인 리트코드 2861번은 합금을 만들기 위한 각 금속의 비율 및 가격이 주어졌을 때 만들 수 있는 최대 개수를 구하는 문제다. 난이도는 Medium이며 이진탐색을 통해 해결할 수 있다.

 

오늘의 문제 - 2861. Maximum Number of Alloys 문제 정보

문제 키워드

- 배열, 이진탐색

난이도

- Medium

 

문제 요약

• n개의 금속과 k가지의 조합법을 통해 합금을 만드려고 한다.
• n개의 금속 각각의 보유량 및 가격, 그리고 예산이 주어졌을 때, 각 조합법을 통해 만들 수 있는 합금의 개수의 최댓값을 구하여라.

 

문제 풀이 과정  

• 만들 수 있는 합금의 개수를 구할 때, 한 조합법만 고려하면 되기 때문에 k가지 조합법에 대해 만들 수 있는 최대 개수를 구해서 비교하여 최댓값을 반환하면 된다.
• 각 조합법에 대해 만들 수 있는 최대 개수를 구하기 위해서, 처음에는 개수를 1씩 늘려가며 예산을 넘기 직전까지 확인하여 구하였다. 하지만 이 방식으로 하면 n과 k가 최대(100개)가 되고 또 예산이 늘어날 수록 계산에 걸리는 시간이 엄청나게 증가한다.
  • 따라서 떠올린 방법은 이진탐색이다. x개를 만들기 위해 필요한 금액을 계산해서, 그 금액이 예산보다 클 때와 작을 때로 구분하여 다음 범위를 설정하며 적절한 개수를 찾는다.

코드

class Solution {
    public int maxNumberOfAlloys(int n, int k, int budget, List<List<Integer>> composition, List<Integer> stock, List<Integer> cost) {
        int answer = 0;

        for(int i =0; i < k; i++){
            int left = 1, right = 200000000;
            int best = 0;

            while(left <= right){
                int mid = (left +right) /2;
                long nowCost = getCost(mid, composition.get(i), stock, cost);

                if(nowCost > budget){
                    right = mid -1;
                } else {
                    left = mid+1;
                    best = mid;
                }
            }

            answer = Integer.max(answer, best);
        }

        return answer;
    }

    private long getCost(int current,List<Integer> composition, List<Integer> stock, List<Integer> cost){
        long totalCost = 0;
        for(int j = 0; j < composition.size(); j++){
            long need = (long) current * composition.get(j) - stock.get(j);
            totalCost += Long.max(need , 0) * cost.get(j);
        }
        return totalCost;
    }
}

• 시간복잡도: O(n * k * log(최대범위))
• 공간복잡도: O(1)