Put Marbles in Bags

문제 설명

• weights 배열이 주어지며, 다음 규칙에 따라 k개의 그룹(가방)으로 나누어야 합니다.
  1. 모든 가방은 비어있으면 안 됩니다.
  2. 연속된 구간을 유지해야 합니다.
     • 즉, weights[i]와 weights[j]가 같은 가방에 있다면, 그 사이의 모든 원소도 같은 가방에 포함되어야 함.
  3. 가방에 속한 가장 왼쪽 값(weights[i])과 오른쪽 값(weights[j])의 합이 해당 가방의 비용이 됩니다.
  4. 모든 가방의 비용을 합한 값이 전체 점수입니다.
• 가능한 모든 k개의 가방 배치 중에서 최대 점수와 최소 점수의 차이를 반환합니다.

문제 풀이

Sorting

💡 아이디어

i를 기준으로 새로운 구간으로 분할하게되면, weights[i] + weights[i + 1] 만큼의 비용이 증가하게 됩니다.

1. 인접한 쌍의 비용 계산 및 정렬
   • weights[i]와 weights[i+1]의 합을 각 구간(쌍)의 비용으로 간주하고, pairWeights에 저장합니다.
     • 예를 들어, weights = [1, 3, 5, 1]이라면, pairWeights = [1+3, 3+5,5+1] = [4, 8, 6]이 됩니다.
   • pairWeights를 오름차순으로 정렬합니다.
2. 최대 점수와 최소 점수 차이 계산
   • 최소 점수: 가장 작은 (k-1)개의 구간을 선택하면 됩니다.
   • 최대 점수: 가장 큰 (k-1)개의 구간을 선택하면 됩니다.
   • pairWeights의 뒤쪽 (큰 값) k-1개에서 앞쪽 (작은 값) k-1개를 뺀 값이 최대 점수와 최소 점수의 차이가 됩니다.

export function putMarbles(weights: number[], k: number): number {
  const n = weights.length;
  const pairWeights: number[] = [];
  for (let i = 0; i < n - 1; i++) {
    pairWeights.push(weights[i] + weights[i + 1]);
  }
  pairWeights.sort((a, b) => a - b);
 
  let answer = 0;
  for (let i = 0; i < k - 1; i++) {
    answer += pairWeights[n - i - 2] - pairWeights[i];
  }
  return answer;
}

복잡도

• 시간 복잡도: $O(n \cdot \log_2n)$
• 공간 복잡도: $O(n)$