[2024] day 89. Leetcode 2958. Length of Longest Subarray With at Most K Frequency

gunny·2024년 3월 28일

2958. Length of Longest Subarray With at Most K Frequency 2958. Length of Longest Subarray With at Most K Frequency python leetcode 2958. Length of Longest Subarray With at Most K Frequency leetcode 2958. Length of Longest Subarray With at Most K Frequency python

코딩테스트

목록 보기

402/530

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 3월 28일 (목)
Leetcode daily problem

2958. Length of Longest Subarray With at Most K Frequency

https://leetcode.com/problems/length-of-longest-subarray-with-at-most-k-frequency/?envType=daily-question&envId=2024-03-28

Problem

정수 배열 nums와 정수 k가 제공 될 때, 배열 내의 요소들의 빈도가 k보다 작거나 같을 때 가장 긴 하위 배열(subarray)의 길이를 반환한다.
하위 배열(subarray)는 배열 내 비어 있지 않은 연속된 요소 시퀀스이다.

Solution

sliding window, two pointer

해당 문제는 주어진 배열의 연속된 하위 배열의 요소들의 빈도가 같이 주어진 정수 k 값보다 작을 때 가장 긴 배열의 길이를 반환하는 것이다.
슬라이딩 윈도우와 투 포인터를 사용해서 해결한다.

먼저 배열의 끝까지 움직이는 하나의 포인터(end)를 할당하고 순환하면서, 해당 요소에 대한 빈도수를 업데이트 한다. 포인터의 시작(start)과 종료(end) 사이의 윈도우(배열의 크기) 사이에 있는 빈도수를 확인하는 것이다.

포인터를 이용해 배열의 인덱스를 할당하고, 배열의 요소의 빈도수를 업데이트한다. 해당 윈도우 사이즈에서 해당 빈도수가 k보다 많아진다면 윈도우의 시작점에 해당하는 left를 오른쪽으로 한칸 이동시키고, 해당 빈도를 제거해나가면서 배열의 max 길이를 업데이트한다.

윈도우의 오른쪽, 즉 배열의 끝에 도달할 때까지 배열의 길이를 업데이트하고 최종 배열의 길이를 반환하면 가장 긴 배열이 반환된다.

여기서 중요한 점은 윈도우의 시작 포인터(start)를 -1로 할당해서 초기에 아무런 원소도 선택하지 않은 상태를 표현해야 한다는 것이다.

알고리즘이 시작될 때, 아직 어떤 원소도 선택되지 않은 상태에서 윈도우의 시작을 표현하기 위해 -1을 할당합니다. 처음에 start를 0으로 설정할 경우, 실제로는 첫 번째 원소를 포함한 상태로 시작하게 된다.

Code

class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        ans, start = 0, -1
        cnt = {}
        for end in range(len(nums)):
            cnt[nums[end]] = cnt.get(nums[end], 0) + 1
            while cnt[nums[end]] > k:
                start +=1
                cnt[nums[start]] -=1
            ans = max(ans, end-start)
        return ans