[리트코드][JAVA] 2861. Maximum Number of Alloys( 합금의 최대 개수)

💡 문제
maximum-number-of-alloys (https://leetcode.com/problems/maximum-number-of-alloys/description/)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

 

📝 선행 개념

---

🤓 문제 풀이

🔨 문제 설명

여러 종류의 금속을 사용하여 합금을 만드는 회사의 소유자입니다. 사용할 수 있는 기계는 k대이며, 각 기계는 합금을 만들기 위해 각 금속 유형의 특정 양을 필요로 합니다.

i번째 기계가 합금을 만들려면, composition[i][j]는 j번째 금속 유형의 단위 수를 필요로 합니다. 초기에는 각 금속 유형에 대해 stock[i]단위의 금속을 가지고 있으며, 금속 유형 i의 구매 비용은 cost[i]코인입니다.

정수 n, k, 예산 budget, 1-인덱스 2차원 배열 composition, 그리고 1-인덱스 배열 stock 및 cost가 주어집니다. 회사가 예산 내에서 최대한 많은 합금을 만드는 것이 목표입니다.

회사가 만들 수 있는 최대 합금 수를 반환합니다.

 

주어진 문제는 여러 종류의 금속을 사용하여 합금을 만드는 회사의 문제입니다. 회사는 k개의 기계를 가지고 있으며, 각 기계는 특정한 금속 구성으로 합금을 생산합니다. 각 기계는 다음과 같은 조건을 가지고 있습니다:

• 각 기계는 composition[i][j] 단위의 j번째 금속을 필요로 합니다.
• 초기에 각 금속 유형의 stock[i] 단위를 보유하고 있으며, 한 단위의 금속을 구매하는 비용은 cost[i]입니다.

목표는 다음과 같습니다:

• 주어진 예산 내에서 가능한 한 많은 수의 합금을 생산하는 것입니다.
• 모든 합금은 동일한 기계를 사용하여 생산해야 합니다.

---

🔨 접근 방법

1. 각 기계별 생산 가능한 합금 수 계산: 각 기계별로 얼마나 많은 합금을 생산할 수 있는지를 계산합니다. 이는 각 기계가 필요로 하는 금속의 양과 현재 보유한 금속 재고를 기준으로 결정됩니다.
2. 예산 내에서 최대 합금 수 계산: 각 기계를 선택했을 때 필요한 총 비용을 계산하고, 주어진 예산 내에서 최대로 생산할 수 있는 합금 수를 계산합니다. 이를 통해 가장 많은 합금을 생산할 수 있는 최적의 기계를 선택합니다.

---

🔨 문제 풀이 과정

 

1. 각 기계별 생산 가능한 합금 수 계산:
   • 각 기계를 순회하면서 해당 기계의 composition을 확인합니다.
   • 각 금속에 대해 필요한 양과 보유한 재고를 비교하여 최대로 생산할 수 있는 합금 수를 계산합니다.
   • 이 값을 maxAlloysWithThisMachine 변수에 저장합니다.
2. 최대 합금 수 계산:
   • 각 기계를 선택했을 때 필요한 총 비용을 계산합니다.
   • 각 금속의 필요한 양과 비용을 곱하여 총 비용을 계산하고, 이를 totalCost 변수에 저장합니다.
   • 주어진 예산 budget 내에서 최대로 생산할 수 있는 합금 수를 계산합니다. 이를 maxPossibleAlloys 변수에 저장합니다.
3. 최대 합금 수 업데이트:
   • 각 기계를 순회하면서 maxPossibleAlloys 값이 가장 큰 경우를 찾아 maxAlloys 변수에 저장합니다.
4. 결과 반환:
   • 모든 기계를 확인한 후에 maxAlloys 값을 반환하여 주어진 조건 내에서 최대 합금 수를 구합니다.

---

🔨 구현코드

import java.util.List;

class Solution {
    // 주어진 예산 내에서 최대 합금 개수를 구하는 함수
    public int maxNumberOfAlloys(int n, int k, int budget, List<List<Integer>> composition, List<Integer> stock, List<Integer> cost) {
        int maxAlloys = 0;// 최대 합금 개수를 저장할 변수
				
        // 각 기계에 대해 최대 합금 개수를 이진 탐색으로 찾음
        for (int machine = 0; machine < k; machine++) {
            int low = 0; // 최소값 초기화
            int high = (int) 1e9; // 10^9으로 high 값을 설정 최대값을 크게 설정 (실제 가능한 최대값 보다 크게 설정)
            
         // 이진 탐색을 이용하여 최대 합금 개수를 찾음
            while (low < high) {
                int mid = (low + high + 1) / 2; // 중간값 계산
                if (canProduceAlloys(n, budget, composition.get(machine), stock, cost, mid)) {
                    low = mid;// 가능하면 low를 늘려서 더 많은 합금을 만들 수 있는지 확인
                } else {
                    high = mid - 1; // 불가능하면 high를 줄여서 더 적은 합금을 만들도록 함
                }
            }
            
            // 현재 기계에서 찾은 최대 합금 개수를 최대값과 비교하여 갱신
            maxAlloys = Math.max(maxAlloys, low);
        }

        return maxAlloys; // 최대 합금 개수 반환
    }
    // 주어진 개수의 합금을 만들 수 있는지 여부를 판단하는 함수
    private boolean canProduceAlloys(int n, int budget, List<Integer> comp, List<Integer> stock, List<Integer> cost, int target) {
        long totalCost = 0; // 총 비용을 저장할 변수
        
        // 각 금속에 대해 필요한 양과 비용을 계산하여 총 비용을 구함
        for (int i = 0; i < n; i++) {
            long required = (long) comp.get(i) * target; // 필요한 금속 양
            if (required > stock.get(i)) { // 재고보다 많이 필요한 경우
                totalCost += (required - stock.get(i)) * cost.get(i); // 추가 구매 비용 계산
                if (totalCost > budget) { // 예산을 초과하면 false 반환
                    return false;
                }
            }
        }

        return totalCost <= budget; // 총 비용이 예산 내에 있는 경우 true 반환
    }
}

---

📚 풀이 보완

코드 설명

1. canProduceAlloys 함수:
   • canProduceAlloys 함수는 주어진 개수의 합금을 만들 수 있는지 여부를 판단합니다.
   • comp 리스트는 현재 기계의 금속 조성을 나타내며, stock은 각 금속의 재고, cost는 각 금속의 구매 비용을 나타냅니다.
   • target은 만들고자 하는 합금의 개수입니다.
   • 필요한 금속의 양을 계산하고, 재고보다 부족한 경우 추가 구매 비용을 계산합니다.
   • 총 비용이 예산을 초과하는 경우 false를 반환하고, 그렇지 않으면 true를 반환합니다.
2. maxNumberOfAlloys 함수:
   • maxNumberOfAlloys 함수는 각 기계별로 최대한 많은 합금을 만들 수 있는지 이진 탐색을 사용하여 찾습니다.
   • composition은 각 기계의 금속 조성을 나타내며, stock과 cost는 각각 금속의 재고와 구매 비용을 나타냅니다.
   • 각 기계에 대해 이진 탐색을 수행하여 최대 합금 개수를 찾습니다.
   • low는 가능한 최대 합금 개수를 찾기 위해 시작하는 값이고, high는 충분히 큰 값을 설정하여 가능한 최대 합금 개수를 탐색합니다.
   • 이진 탐색을 통해 각 기계에서 가능한 최대 합금 개수를 찾고, 이 중에서 가장 큰 값을 maxAlloys에 저장하여 반환합니다.

 

이번 문제는 풀기가 어려웠다 테스트 케이스를 여러개 추가를 하면서 확인을 했다. 

내가 실패한 이유는

1. canProduce 함수가 모든 기계를 제대로 확인하지 않고, 첫 번째 가능한 기계에서 true를 반환하도록 작성되어 정확한 판단을 하지 못함.
2. 이진 탐색의 high 값을 예산으로 설정하여 실제 최대 합금 개수를 제대로 탐색하지 못함.

이후 통과를 할 수 있었던 이유는

1. 각 기계별로 최대 합금 개수를 정확히 계산하여 최댓값을 반환함.
2. 이진 탐색 범위를 충분히 크게 설정하여 실제 가능한 최대 합금 개수를 탐색함.

---

📍 Plus+

공간 복잡도

추가적인 데이터 구조를 생성하지 않고 입력으로 주어진 변수들만을 사용하므로, O(1)의 공간 복잡도를 가집니다.

시간복잡도

• totalCost 함수는 주어진 금속 구성과 재고, 비용을 바탕으로 mid 개의 합금을 만들기 위한 총 비용을 계산합니다.
• 금속의 종류를 나타내는 n에 대해 O(n) 시간이 소요됩니다.
• canProduce 함수는 각 기계별로 mid 개의 합금을 만들 수 있는지 확인합니다.
• 기계의 수를 나타내는 k에 대해 O(k * n) 시간이 소요됩니다 (모든 기계와 그에 따른 금속 구성을 확인해야 하므로).
• 따라서 canProduce 함수의 시간 복잡도는 O(k * n)
• maxNumberOfAlloys 함수는 이진 탐색을 사용하여 최대 합금 수를 찾습니다.
• 이진 탐색에서는 low와 high의 값이 각각 budget과 1e9로 초기화되어 있으며, 이진 탐색을 수행할 때마다 반씩 범위를 줄여나가므로 O(log budget)의 시간이 소요됩니다.
• canProduce 함수의 호출은 O(k * log budget) 시간이 소요됩니다.
• 따라서 maxNumberOfAlloys 함수의 시간 복잡도는 O(k * n * log budget)

요약

• 공간 복잡도 : O(1)
• 시간 복잡도 : O(k * n * log budget)