[리트코드][JAVA] 2551. Put Marbles in Bags (구슬을 가방에 담다)

💡 문제
Put Marbles in Bags (https://leetcode.com/problems/put-marbles-in-bags/description/)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

 

📝 선행 개념

 

---

🤓 문제 풀이

문제 해석:

1- 주어진 배열 weights에는 각 구슬의 무게가 저장되어 있습니다. 또한 정수 k가 주어집니다. 이 배열에서 k개의 가방에 구슬을 다음 규칙에 따라 나누려고 합니다:

1. 어떤 가방도 비어 있지 않아야 합니다.
2. i번째 구슬과 j번째 구슬이 같은 가방에 있다면, i부터 j번째 인덱스에 있는 모든 구슬도 같은 가방에 있어야 합니다.
3. 한 가방에 속한 구슬의 인덱스 범위가 i부터 j이면, 해당 가방의 비용은 weights[i] + weights[j]입니다.
4. 구슬을 배분한 후의 점수는 모든 가방의 비용의 합입니다.

주어진 조건에 따라 구슬을 배분한 후 최대 점수와 최소 점수의 차이를 반환하는 문제입니다.

---

2-

여러 개의 가방이 있습니다. 0부터 인덱스가 시작되는 정수 배열 weights가 주어집니다. 여기서 weights[i]는 i번째 구슬의 무게입니다. 또한 정수 k가 주어집니다.

다음 규칙에 따라 구슬을 k개의 가방에 나눕니다:

1. 어떤 가방도 비어 있지 않아야 합니다.
2. i번째 구슬과 j번째 구슬이 같은 가방에 있으면, i부터 j번째 인덱스에 있는 모든 구슬도 같은 가방에 있어야 합니다.
3. 한 가방에 속한 구슬의 인덱스 범위가 i부터 j일 때, 해당 가방의 비용은 weights[i] + weights[j]입니다.
4. 구슬을 배분한 후의 점수는 모든 가방의 비용의 합입니다.

구슬을 배분한 후 최대 점수와 최소 점수의 차이를 반환합니다.

---

입출력

예시 1:

입력: weights = [1,3,5,1], k = 2 출력: 4 설명: 배분 [1],[3,5,1]은 최소 점수가 (1+1) + (3+1) = 6입니다. 배분 [1,3],[5,1]은 최대 점수가 (1+3) + (5+1) = 10입니다. 따라서, 그들의 차이인 10 - 6 = 4를 반환합니다.

예시 2:

입력: weights = [1, 3], k = 2 출력: 0 설명: 가능한 배분은 [1],[3]뿐입니다. 최대 점수와 최소 점수가 동일하므로, 0을 반환합니다.

제한 사항:

1 <= k <= weights.length <= 105 1 <= weights[i] <= 109

---

 

문제는 weights 배열과 **k**가 주어졌을 때, k개의 가방에 구슬을 나누어 넣고, 최대 점수와 최소 점수의 차이를 구하는 것입니다.

여기서, 점수는 각 가방의 첫 번째와 마지막 구슬의 가중치 합

 

import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public long putMarbles(int[] weights, int k) {
        int n = weights.length;
        
        // k가 n과 같으면 각 구슬이 하나씩 가방에 들어가므로 점수 차이는 0
        if (k == n) return 0;
        
        // 인접한 두 구슬의 가중치 합을 저장할 배열
        int[] costs = new int[n - 1];
        
        // 인접한 두 구슬의 가중치 합을 계산
        for (int i = 0; i < n - 1; i++) {
            costs[i] = weights[i] + weights[i + 1];
        }
        
        // costs 배열을 오름차순으로 정렬
        Arrays.sort(costs);
        
        long min = 0, max = 0;
        
        // 최소 점수를 구하기 위해 k-1개의 가장 작은 비용을 더함
        for (int i = 0; i < k - 1; i++) {
            min += costs[i];
        }
        
        // 최대 점수를 구하기 위해 k-1개의 가장 큰 비용을 더함
        for (int i = 0; i < k - 1; i++) {
            max += costs[n - i - 2];
        }
        
        // 최대 점수와 최소 점수의 차이를 반환
        return max - min;
    }
}

---

📚 풀이 보완

코드 설명:

1. 입력 검증: **k**가 **weights**의 길이와 같으면 모든 구슬이 각각의 가방에 들어가므로 점수 차이는 0입니다.
2. 인접 구슬의 비용 계산: weights 배열에서 인접한 두 구슬의 합을 계산하여 costs 배열에 저장합니다.
3. 비용 정렬: costs 배열을 오름차순으로 정렬합니다.
4. 최소 점수 계산: costs 배열에서 가장 작은 **k-1**개의 비용을 더하여 최소 점수를 계산합니다.
5. 최대 점수 계산: costs 배열에서 가장 큰 **k-1**개의 비용을 더하여 최대 점수를 계산합니다.
6. 점수 차이 반환: 최대 점수와 최소 점수의 차이를 반환합니다.

---

📍 Plus+

문제 해석하고 풀어보는 단계가 나에게는 쉽지는 않았다.

다른 사람들 풀이를 봤는데 띵언..

 

- 10줄짜리 쉬운 솔루션

- 간단한 JAVA 솔루션이 100% 승리합니다!

 

멋지군..