[LeetCode] 2461. Maximum Sum of Distinct Subarrays With Length K - Python

 

 

 

난이도: Medium

문제 설명

---

You are given an integer array nums and an integer k. Find the maximum subarray sum of all the subarrays of nums that meet the following conditions:

• The length of the subarray is k, and
• All the elements of the subarray are distinct.

Return the maximum subarray sum of all the subarrays that meet the conditions. If no subarray meets the conditions, return 0.

A subarray is a contiguous non-empty sequence of elements within an array.

 

문제 예제

---

Example 1:

Input: nums = [1,5,4,2,9,9,9], k = 3
Output: 15
Explanation: The subarrays of nums with length 3 are:
- [1,5,4] which meets the requirements and has a sum of 10.
- [5,4,2] which meets the requirements and has a sum of 11.
- [4,2,9] which meets the requirements and has a sum of 15.
- [2,9,9] which does not meet the requirements because the element 9 is repeated.
- [9,9,9] which does not meet the requirements because the element 9 is repeated.
We return 15 because it is the maximum subarray sum of all the subarrays that meet the conditions

Example 2:

Input: nums = [4,4,4], k = 3
Output: 0
Explanation: The subarrays of nums with length 3 are:
- [4,4,4] which does not meet the requirements because the element 4 is repeated.
We return 0 because no subarrays meet the conditions.

 

제한 사항

---

• 1 <= k <= nums.length <= 105
• 1 <= nums[i] <= 105

 

✏️ 내 풀이

class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        d = deque()
        check_distinct = defaultdict(int)
        answer, now_sum = 0, 0
        len_d, len_cd = 0, 0

        for num in nums:
            d.append(num)
            now_sum += num
            len_d += 1
            check_distinct[num] += 1

            if check_distinct[num] == 1:
                len_cd += 1

            if len_d > k:
                left = d.popleft()
                len_d -= 1
                now_sum -= left
                check_distinct[left] -= 1

                if not check_distinct[left]:
                    check_distinct.pop(left)
                    len_cd -= 1

            if len_cd == k and len_d == k:
                answer = max(answer, now_sum)

        return answer

 

이 문제는 nums에 있는 요소들을 현재 요소를 포함해 다음 k-1개의 요소들로 subarray를 만들었을 때, 그 합이 최대가 되는 값을 구하면 되는 문제였다. 하지만 subarray에 중복은 있어서는 안된다.

 

예를 들어, Input이 nums: [1, 5, 4, 2, 9, 9, 9], k = 3와 같을 때,

- [1, 5, 4]

- [5, 4, 2]

- [4, 2, 9]

- [2, 9, 9]

- [9, 9, 9]

다음과 같이 subarray를 구할 수 있다.

하지만 위에 [2, 9, 9]와 [9, 9, 9] subarray들을 9가 중복되기 때문에 사용할 수 없다.

 

나는 deque와 defaultdict를 이용해 이를 풀었다.

 

nums에 모든 요소를 탐색하면서, deque에 현재 요소를 넣어주었고,

만약 deque의 길이가 k보다 많아지면 맨 앞쪽 요소를 빼주는 작업을 진행했다.

 

또한 중복된 값을 확인하기 위해 defaultdict을 만들어 요소가 나올 때마다 요소 별로 +1을 해주었고, 맨 앞쪽 요소가 빠지게될때는 -1을 해줌으로써 이를 관리했다.

 

모든 조건에 맞으면 max함수를 통해 결과 값을 구할 수 있었다.

 

아래 그림은 nums의 요소를 탐색할 때마다 일어나는 과정을 보여준다.

 

 

deque의 길이와 defaultdict의 길이가 모두 k와 일치하면 현재 subarray의 합과 answer를 비교해 더 큰 값으로 answer를 업데이트 해주는 것을 확인할 수 있다.

 

또한, 조건을 만족하지 않으면 다음 요소로 넘어가 진행하는 것도 확인할 수 있다.

 

이 문제는 중복관리를 어떻게 할지만 떠오르면 쉽게 풀 수 있는 듯한 문제였다.

나는 defaultdict을 사용해서 중복관리를 했지만, 더 좋은 방법이 있을 수도 있을 것 같다.

---

[LeetCode] 2461. Maximum Sum of Distinct Subarrays With Length K