2386. Find the K-Sum of an Array / TypeScript

 

You are given an integer array nums and a positive integer k. You can choose any subsequence of the array and sum all of its elements together.

 

We define the K-Sum of the array as the kth largest subsequence sum that can be obtained (not necessarily distinct).

Return the K-Sum of the array.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Note that the empty subsequence is considered to have a sum of 0.

 

Example 1:

Input: nums = [2,4,-2], k = 5
Output: 2
Explanation: All the possible subsequence sums that we can obtain are the following sorted in decreasing order:
- 6, 4, 4, 2, 2, 0, 0, -2.
The 5-Sum of the array is 2.

Example 2:

Input: nums = [1,-2,3,4,-10,12], k = 16
Output: 10
Explanation: The 16-Sum of the array is 10.

 

출처 : https://leetcode.com/problems/find-the-k-sum-of-an-array/description/

 

 

풀이

function kSum(nums: number[], k: number): number {
   let pq = new MaxPriorityQueue(), sum = 0, n = nums.length;

    nums.sort((a,b) => Math.abs(a) - Math.abs(b));
    
    for(let i = 0 ; i < n ; i++){
        if(nums[i] > 0) sum += nums[i];
    }
    
    pq.enqueue(0, sum);
    let q;
    while(k--){
        q = pq.dequeue();
        if(q.element < n){
            pq.enqueue(q.element+1, q.priority - Math.abs(nums[q.element]));
            if(q.element>0) pq.enqueue(q.element+1, q.priority + Math.abs(nums[q.element-1]) - Math.abs(nums[q.element]));
        }
    }
    return q.priority;
};

배열 nums와 양의 정수 k가 주어질 때, 배열에서 가능한 모든 부분수열의 합 중에서 k번째로 큰 값을 찾는 문제

kSum는 nums라는 숫자 배열과 k라는 정수를 입력받아 특정 계산을 통해 값을 반환하는 알고리즘

 

 

• 우선순위 큐 생성:
  pq는 MaxPriorityQueue (최대 우선순위 큐)라는 구조로, 항상 가장 높은 우선순위(값)를 가진 요소를 먼저 처리.
  • sum은 양수 숫자들의 합을 저장하기 위한 변수. n은 nums 배열의 길이를 저장
• 배열 정렬:
  nums 배열은 절대값 기준으로 오름차순 정렬. 즉, 값의 크기와 상관없이 절대값이 작은 순서대로 정렬
• 양수의 합 계산:
  nums 배열에서 양수들만 더해 sum에 저장
• 큐에 첫 번째 값 삽입:
  우선순위 큐 pq에 첫 번째 요소로 0과 sum을 삽입.
  • 여기서 0은 배열의 인덱스를 의미하고, sum은 현재까지의 양수들의 합
• k번 동안 루프:
  k번의 반복문을 통해 pq에서 가장 우선순위가 높은 요소를 꺼내 처리. 꺼낸 요소의 인덱스가 배열 길이(n)보다 작을 때, 두 가지 경우를 처리:
  • 현재 요소의 인덱스(q.element)에 해당하는 값을 뺀 결과를 큐에 삽입.
  • 바로 전 요소(q.element - 1)와 현재 요소의 차이를 큐에 삽입하여, 이전 값을 빼고 새로운 값을 더한 결과를 처리.
• 최종 결과 반환:
  반복이 끝나면 마지막으로 꺼낸 q.priority 값이 결과로 반환. q.priority는 가장 큰 값을 추적하여 최종 결과를 의미

 

MaxPriorityQuene()

이 자료구조는 항상 가장 큰 우선순위를 가진 요소를 먼저 처리하는 큐.

우선순위 큐는 일반적인 큐와는 다르게 요소들이 추가되는 순서에 관계없이 우선순위에 따라 정렬되고, 가장 높은 우선순위를 가진 요소가 먼저 나옴.

우선순위 큐의 특징

1. 최대 우선순위 큐(Max Priority Queue):
   • 가장 큰 값 또는 우선순위가 가장 높은 요소가 먼저 나.
   • 예를 들어, 값이 5, 3, 8인 요소가 있으면, 우선순위 큐에서 8이 가장 먼저 처리됩니다.
2. 최소 우선순위 큐(Min Priority Queue):
   • 반대로 가장 작은 값 또는 우선순위가 가장 낮은 요소가 먼저 처리됨.
   • 위와 같은 예시에서는 3이 먼저 나옴.

주요 메서드

• enqueue(element, priority): 큐에 element를 우선순위 priority와 함께 추가. 우선순위가 높은 순서대로 정렬.
• dequeue(): 현재 큐에서 우선순위가 가장 높은 요소를 제거하고 반환
• peek(): 큐에서 가장 우선순위가 높은 요소를 제거하지 않고 반환
• size(): 큐에 있는 요소의 수를 반환

MaxPriorityQueue 사용 예시

const pq = new MaxPriorityQueue();

// 요소 추가 (값, 우선순위)
pq.enqueue("task1", 5);
pq.enqueue("task2", 1);
pq.enqueue("task3", 3);

// 우선순위가 높은 요소부터 반환
console.log(pq.dequeue().element);  // "task1" (우선순위 5)
console.log(pq.dequeue().element);  // "task3" (우선순위 3)
console.log(pq.dequeue().element);  // "task2" (우선순위 1)

 

예시 nums = [2, 4, -2],  k = 5

 

1. 배열 정렬

먼저 nums 배열을 절대값 기준으로 오름차순으로 정렬

nums.sort((a, b) => Math.abs(a) - Math.abs(b))

 

 

절대값을 기준으로 정렬하면:

nums = [2, -2, 4]

 

 

2. 양수들의 합 계산

이제 배열에서 양수 값들을 더해 sum을 계산

• 2는 양수이므로 더함 → sum = 2
• -2는 음수이므로 패스
• 4는 양수이므로 더함 → sum = 2 + 4 = 6

따라서, 양수들의 합은 sum = 6

 

3. 우선순위 큐에 초기값 삽입

우선순위 큐에 첫 번째 요소를 삽입

pq.enqueue(0, sum) // pq.enqueue(0, 6)

 

큐 상태:

pq = [(0, 6)]

 

4. k번 반복 (k = 5)

이제 k = 5번 반복하면서 큐에서 가장 높은 우선순위 값(즉, 가장 큰 합)을 꺼내고, 다음 가능한 값을 큐에 삽입하는 과정을 진행.

첫 번째 반복 (k = 5):

• pq.dequeue()로 우선순위가 가장 높은 (0, 6)을 꺼냄. 즉, 현재 인덱스 0, 우선순위 6.
• 인덱스 1로 넘어가며 가능한 경우를 계산:
  1. 현재 인덱스 0의 값을 제외하고 큐에 삽입 → pq.enqueue(1, 6 - |nums[0]|) = pq.enqueue(1, 6 - 2) = pq.enqueue(1, 4)
  2. 이전 값이 없으므로 두 번째 경우는 무시

큐 상태:

pq = [(1, 4)]

 

• k = 4로 줄어듬.

두 번째 반복 (k = 4):

• (1, 4)을 꺼냄. 다음 인덱스 2로 넘어감
  1. 현재 값(-2)을 제외한 경우: pq.enqueue(2, 4 - |nums[1]|) = pq.enqueue(2, 4 - 2) = pq.enqueue(2, 2)
  2. 이전 값(2)를 포함하고 현재 값을 제외한 경우: pq.enqueue(2, 4 + |nums[0]| - |nums[1]|) = pq.enqueue(2, 4 + 2 - 2) = pq.enqueue(2, 4)

큐 상태:

pq = [(2,2),(2,4)]

 

• k = 3로 줄어듬.

세 번째 반복 (k = 3):

• (2, 4)를 꺼냄. 인덱스 3 넘어가며 다음 값을 계산:
  1. 현재 값(4)을 제외한 경우: pq.enqueue(3, 4 - |nums[2]|) = pq.enqueue(3, 4 - 4) = pq.enqueue(3, 0)
  2. 이전 값(-2)를 포함하고 현재 값을 제외한 경우: pq.enqueue(3, 4 + |nums[1]| - |nums[2]|) = pq.enqueue(2, 4 + 2 - 4) = pq.enqueue(3, 2)

큐 상태:

pq = [(2, 2),(3,0),(3,2)]

 

• k = 2로 줄어듬.

네 번째 반복 (k = 2):

• (2, 2)을 꺼냄. 인덱스는 이미 배열의 끝에 도달했기 때문에 더 이상 추가할 값은 없음.
• k = 1로 줄어듬.

다섯 번째 반복 (k = 1):

• (3, 2)를 꺼냅니다. 마지막으로 꺼낸 값.

5. 최종 결과

k = 5번 반복 후 최종적으로 큐에서 꺼낸 값이 최종 결과가 됨. 이 값은 2