[leetcode] Length of Longest Subarray With at Most K Frequency

문제

• 링크
• 배열 nums와 정수 k가 주어진다. 특정 값의 빈도수가 subarray 안에서 k를 넘지 않으면 good인 상태라고 한다. subarray에 속한 모든 값이 good인 subarray의 최대 길이를 구해야 한다.
• 제약 조건
  • 배열 길이: 1 <= nums.length <= 10^5
  • 값 범위: 1 <= nums[i] <= 10^9
  • k 범위: 1 <= k <= nums.length

풀이

풀기 전

• 공간 복잡도 제약이 없는 문제라 반가웠다.
• 빈도수를 세면서 빠르게 접근할 수 있으려면 map을 써야될 거 같다. 그리고 투 포인터 방식으로 배열을 순회하면서, 조건을 만족하는 가장 긴 subarray를 찾을 수 있다.

코드

class Solution {
    public int maxSubarrayLength(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();

        int ans = 0;
        int left = 0, right = 0;
        for (; right < nums.length; right++) {
            int num = nums[right];  // 순회하는 값을 right로 가져온다.
            int freq = map.getOrDefault(num, 0) + 1;  // 현재 값의 빈도수를 맵에서 가져온다.

			// 만약 빈도수가 k보다 크면 조건을 만족하지 못한다.
            // 현재 값과 동일한 값을 찾을 때까지 left를 증가시키며 map에서도 빈도수를 업데이트 해줘야 한다.
            if (freq > k) {
                while (true) {
                    int tmp = nums[left];
                    left++;

                    if (tmp == num)  // 현재 값과 동일한 값을 찾으면 루프 종료한다.
                        break;
                    else  // 현재 값과 다른 값을 찾으면 map에서 하나 빼주고 다시 반복한다.
                        map.put(tmp, map.get(tmp) - 1);
                }
                // 현재 값의 빈도수에서 1 빼준다.
                freq--;
            }
            // 현재 값의 빈도수를 업데이트 한다.
            map.put(num, freq);

			// 현재 subarray 길이와 이전에 찾은 최대 길이 중 큰 값을 취한다.
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

푼 후

• 이전 문제들에서 map을 못 쓰기도 했고 투 포인터 방식으로 풀어보기도 해서, 이 문제는 쉽게 풀렸다.