nums and an integer k.
The frequency of an element x is the number of times it occurs in an array.
An array is called good if the frequency of each element in this array is less than or equal to k.
Return the length of the longest good subarray of nums.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [1,2,3,1,2,3,1,2], k = 2 Output: 6 Explanation: The longest possible good subarray is [1,2,3,1,2,3] since the values 1, 2, and 3 occur at most twice in this subarray. Note that the subarrays [2,3,1,2,3,1] and [3,1,2,3,1,2] are also good. It can be shown that there are no good subarrays with length more than 6.
Example 2:
Input: nums = [1,2,1,2,1,2,1,2], k = 1 Output: 2 Explanation: The longest possible good subarray is [1,2] since the values 1 and 2 occur at most once in this subarray. Note that the subarray [2,1] is also good. It can be shown that there are no good subarrays with length more than 2.
Example 3:
Input: nums = [5,5,5,5,5,5,5], k = 4 Output: 4 Explanation: The longest possible good subarray is [5,5,5,5] since the value 5 occurs 4 times in this subarray. It can be shown that there are no good subarrays with length more than 4.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1091 <= k <= nums.length배열, 해시 테이블, 슬라이딩 윈도우
이 문제는 정수 배열 nums와 정수 k가 주어졌을 때, 배열 내에서 각 숫자의 등장 빈도가 k 이하인 가장 긴 "좋은(good)" 부분 배열의 길이를 찾는 것을 요구합니다. 여기서 "부분 배열(subarray)"은 원래 배열 내에서 연속된 요소들의 집합을 의미합니다.
nums: 양의 정수로 이루어진 배열.k: 각 요소의 최대 허용 빈도를 나타내는 양의 정수.k 이하인 가장 긴 부분 배열의 길이.nums의 길이는 최대 10^5, nums[i] 값은 10^9까지, k는 1부터 nums.length까지입니다.이 문제는 "연속된 부분 배열"에서 어떤 조건을 만족하는 "가장 긴" 길이를 찾는 전형적인 문제입니다. 이러한 유형의 문제에는 슬라이딩 윈도우 (Sliding Window) 알고리즘이 매우 효과적입니다.
슬라이딩 윈도우는 두 개의 포인터(left와 right)를 사용하여 배열의 특정 구간(윈도우)을 유지하고, 이 윈도우를 배열 위에서 이동시키면서 조건을 검사하는 방식입니다.
여기서는 윈도우 내 각 요소의 빈도를 빠르게 추적하고 업데이트해야 하므로, **해시 맵 (Hash Map 또는 Dictionary)**을 함께 사용하여 각 숫자의 빈도를 저장하고 관리합니다. defaultdict를 사용하면 키가 없는 경우 자동으로 기본값(정수의 경우 0)으로 초기화되므로 편리합니다.
전략은 다음과 같습니다:
right 포인터를 사용하여 윈도우를 점차 확장합니다.k를 초과하면, 현재 윈도우는 "좋지 않은" 상태가 됩니다.left 포인터를 이동시키면서 윈도우의 시작 부분을 축소하고, 해당 요소들의 빈도를 해시 맵에서 감소시킵니다.제공된 코드는 슬라이딩 윈도우와 해시 맵을 사용하여 문제를 해결합니다.
n = len(nums): 입력 배열 nums의 총 길이를 n에 저장합니다.left = 0, right = 0: 슬라이딩 윈도우의 시작(left)과 끝(right)을 나타내는 두 개의 포인터를 모두 배열의 첫 번째 인덱스(0)로 초기화합니다. right 포인터는 현재 윈도우에 추가될 다음 요소의 인덱스를 가리키는 역할을 합니다.counts = defaultdict(int): 윈도우 내 각 숫자의 등장 횟수를 저장하기 위한 해시 맵(딕셔너리)을 초기화합니다. defaultdict(int)를 사용하면 특정 숫자가 아직 딕셔너리에 없을 경우, 접근 시 자동으로 0으로 초기화됩니다.answer = 0: 지금까지 찾은 가장 긴 '좋은' 부분 배열의 길이를 저장할 변수를 0으로 초기화합니다.while right != n: 루프는 right 포인터가 배열의 끝(n)에 도달할 때까지 계속됩니다. 이 루프는 right 포인터를 통해 윈도우를 한 칸씩 확장하는 역할을 합니다.counts[nums[right]] += 1: right 포인터가 가리키는 현재 숫자를 윈도우에 포함시키고, 해당 숫자의 빈도를 1 증가시킵니다.while counts[nums[right]] > k:: 방금 윈도우에 추가된 nums[right]의 빈도가 k를 초과했는지 확인합니다. 이 조건이 참이면, 현재 윈도우는 "좋지 않은" 상태입니다.left 포인터를 오른쪽으로 이동시키면서 윈도우의 시작 부분을 축소합니다.counts[nums[left]] -= 1: left 포인터가 가리키는 nums[left]를 윈도우에서 제거하고, 해당 숫자의 빈도를 1 감소시킵니다.left += 1: left 포인터를 한 칸 오른쪽으로 이동시킵니다. 이 과정은 nums[right]의 빈도가 다시 k 이하가 되어 윈도우가 "좋은" 상태가 될 때까지 반복됩니다.right += 1: left 포인터 이동으로 윈도우가 "좋은" 상태가 되면 (또는 애초에 k를 초과하지 않았다면), 이제 right 포인터를 한 칸 오른쪽으로 이동시켜 윈도우를 다음 단계로 확장할 준비를 합니다. (다음 반복에서 새로운 nums[right]를 처리하게 됩니다.)answer = max(answer, right - left): 현재 left와 right 포인터 사이의 윈도우(nums[left]부터 nums[right-1]까지)는 항상 "좋은" 상태임이 보장됩니다. 이 윈도우의 길이(right - left)를 기존 answer와 비교하여 더 큰 값을 answer에 저장합니다.return answer: right 포인터가 배열의 끝에 도달하여 모든 가능한 부분 배열을 검사한 후, answer에 저장된 가장 긴 '좋은' 부분 배열의 길이를 최종 결과로 반환합니다.시간 복잡도: O(N)
left와 right 두 포인터는 배열 nums를 최대 한 번씩 순회합니다. right 포인터는 배열의 시작부터 끝까지 한 방향으로만 이동하며, left 포인터 또한 right 포인터와 마찬가지로 한 방향으로만 이동합니다.counts 딕셔너리에 한 번 추가되고, while counts[nums[right]] > k: 조건에 따라 딕셔너리에서 최대 한 번 제거될 수 있습니다. 딕셔너리 연산(추가, 감소, 조회)은 평균적으로 O(1)의 시간이 소요됩니다.N개의 요소에 대해 일정한 작업이 수행되므로, 시간 복잡도는 O(N)입니다.공간 복잡도: O(U)
counts 딕셔너리는 현재 슬라이딩 윈도우 내에 있는 고유한 숫자들의 빈도를 저장합니다.nums 배열의 모든 숫자가 서로 다른 경우 딕셔너리에는 최대 N개의 엔트리가 저장될 수 있습니다. (여기서 U는 nums 배열에 있는 고유한 숫자의 개수를 의미하며, U <= N입니다.)left와 right 두 포인터를 활용하여 효율적으로 부분 배열을 탐색합니다. right 포인터로 윈도우를 확장하고, 조건(빈도 > k) 위반 시 left 포인터로 윈도우를 축소하는 접근 방식은 연속된 부분 배열의 최대/최소 길이를 찾는 문제에서 매우 효과적입니다.defaultdict)을 이용한 빈도 관리: 현재 슬라이딩 윈도우 내 각 숫자의 등장 횟수를 O(1)의 평균 시간 복잡도로 빠르게 추적하고 업데이트하기 위해 해시 맵(defaultdict(int))을 사용합니다. 이는 '각 요소의 빈도가 k 이하'라는 핵심 조건을 실시간으로 검사하고 유지하는 데 필수적인 자료구조입니다.right 포인터를 전진시키면서 윈도우를 확장하고, 동시에 while counts[nums[right]] > k: 조건을 통해 윈도우가 "좋지 않은" 상태가 되면 left 포인터를 전진시켜 윈도우를 축소하는 로직이 핵심입니다. 이 동적인 윈도우 조정 덕분에 항상 유효한(좋은) 부분 배열에 대해서만 최대 길이를 갱신할 수 있습니다.from collections import defaultdict
class Solution:
def maxSubarrayLength(self, nums: List[int], k: int) -> int:
n = len(nums)
left = 0
right = 0
counts = defaultdict(int)
answer = 0
while right != n:
counts[nums[right]] += 1
while counts[nums[right]] > k:
counts[nums[left]] -= 1
left += 1
right += 1
answer = max(answer, right - left)
return answer