99클럽 코테 스터디 7일차 TIL - 정렬

항해99 코테 스터디 7일차 문제인 LeetCode의 'Put Marbles in Bags'은 N개의 구슬을 k개의 그룹으로 나눴을 때 무게의 최댓값과 최솟값의 차를 구하는 문제다. 난이도는 Hard이며 정렬을 통해 해결할 수 있다.

 

오늘의 문제 - Put Marbles in Bags 문제 정보

문제 키워드

- 정렬

난이도

- Hard

 

문제 요약

• 각 구슬의 무게를 나타내는 weights 배열이 주어진다.
• 아래의 규칙에 따라 구슬을 k개의 가방에 나누어 담아라.
  • 어떤 가방도 비어있지 않다.
  • i번째 구슬과 j번째 구슬이 같은 가방에 들어있다면, i+1~j-1번째 구슬도 모두 같은 가방에 들어있다.
  • i번째 구슬부터 j번째 구슬까지만 들어있다면, 그 가방의 무게는 weights[i]+weights[j]이다.
• score = (가방 k개의 무게의 합)
• 가능한 score의 최댓값과 최솟값의 차를 구하라.

 

문제 풀이 과정  

• 가방에는 연속된 구슬끼리만 들어갈 수 있으므로, 전체 구슬 배열을 k개로 자르는 것으로 경우의 수를 구할 수 있다.
• i번째에서 자르면, 총합에는 weights[i] + weights[i+1]가 추가되는데, 총 k개로 잘라야 하므로 k-1번의 weights[i]+weights[i+1]가 더해진다.
• 맨앞과 맨뒤 구슬의 무게는 어떻게하든 반드시 더해지므로, 최댓값과 최솟값의 차를 구할 때 상쇄되므로 무시한다.
• 따라서 weights[i]+weights[i+1]의 최대 k-1개의 합이 최댓값, 최소 k-1개의 합이 최솟값이 된다.

코드

class Solution {
    public long putMarbles(int[] weights, int k) {
        int N = weights.length;
        int[] cutWeights = new int[N-1];
        for(int i=0; i<N-1; i++) {
            cutWeights[i] = weights[i] + weights[i+1];
        }

        Arrays.sort(cutWeights);
        long minSum = 0;
        long maxSum = 0;

        for(int i=0; i<k-1; i++) {
            minSum += cutWeights[i];
            maxSum += cutWeights[N-i-2];
        }

        return maxSum - minSum;
    }
}

• 시간복잡도: O(NlogN)
• 공간복잡도: O(N)

 

오늘의 학습 회고

새롭게 알게된 것

• 문제를 단순화하여 풀면 쉽게 풀 수 있다.
  • 너무 어렵게 생각하려다가 쉬운 해결방법을 발견하지 못했다.