[leetcode] Subarrays with K Different Integers

문제

• 링크
• 배열 nums와 정수 k가 주어진다. 서로 다른 값의 개수가 정확히 k인 subarray의 총 개수를 구해야 한다.
• 제약 조건
  • 배열 길이: 1 <= nums.length <= 2 * 10^4
  • 배열 값과 k 범위: 1 <= nums[i], k <= nums.length

풀이

풀기 전

• 머리를 이리저리 굴려봤는데 마땅한 풀이가 떠오르지 않았다. 배열을 순회하면서 조건을 만족하는 범위를 체크하면 될 거 같은데 어떻게 체크할지가 애매했다.
• 그러다가 특정 인덱스에서 조건을 만족하는 가장 작은 범위와 가장 큰 범위를 찾으면 해당 인덱스에서의 subarray 개수를 구할 수 있을 거 같았다. 그래서 map을 두개 둔 뒤에 하나는 작은 범위를 찾는 용으로, 하나는 큰 범위를 찾는 용으로 사용했다.

코드

class Solution {
    public int subarraysWithKDistinct(int[] nums, int k) {
        HashMap<Integer, Integer> map1 = new HashMap<>();  // 큰 조건 범위 찾는 용도
        HashMap<Integer, Integer> map2 = new HashMap<>();  // 작은 조건 범위 찾는 용도
        int ans = 0;

        int lastMeet = 0, firstMeet = 0;
        for (int i=0; i<nums.length; i++) {
            int num = nums[i];
            map1.put(num, map1.getOrDefault(num, 0) + 1);
            map2.put(num, map2.getOrDefault(num, 0) + 1);

			// 아직 k개를 담지 못했으면 계속 진행한다.
            if (map1.size() < k)
                continue;

            int tmp;
            // 큰 조건 범위를 찾는다.
            // map 크기가 k와 처음 같아지는 순간이 가장 큰 조건 범위이다.
            while (map1.size() != k) {
                tmp = nums[lastMeet];
                map1.put(tmp, map1.get(tmp) - 1);
                if (map1.get(tmp) == 0)
                    map1.remove(tmp);
                lastMeet++;
            }

			// 작은 조건 범위를 찾는다.
            // map 크기가 k와 같으면서 map 값이 1인 인덱스가 가장 작은 조건 범위이다.
            // 해당 값을 map에서 빼는 순간 map 크기가 k 보다 작아지기 때문이다.
            while (map2.size() != k || map2.get(nums[firstMeet]) != 1) {
                tmp = nums[firstMeet];
                map2.put(tmp, map2.get(tmp) - 1);
                if (map2.get(tmp) == 0)
                    map2.remove(tmp);
                firstMeet++;
            }

			// (작은 조건 범위 인덱스) - (큰 조건 범위 인덱스) + 1을 더해준다.
            ans += firstMeet - lastMeet + 1;
        }
        return ans;
    }
}

• 시간 복잡도는 O(nums.length)이다. 순회하는 인덱스들이 nums를 한 번씩만 순회하고 있다.
• 공간 복잡도는 O(nums.length)이다. map에는 nums에 있는 값들이 들어가기 때문이다.

푼 후

• 어찌어찌 풀긴 했는데 테스트 케이스가 큰지 생각보다 실행 시간이 오래 걸렸다.
• 다른 사람 코드를 보니 아이디어가 비슷한 듯 달랐다. 서로 다른 값이 최대 k개인 subarray 개수에서 서로 다른 값이 최대 k-1인 subarray 개수를 빼주고 있었다. 그럼 서로 다른 값이 정확히 k인 subarray 개수만 남게 된다. 보고 나면 간단한 아이디어인데, 생각하기가 쉽지 않은 거 같다. 문제에서 정확한 개수와 관련된 조건이 있을 때, 전체에서 부분을 빼는 방식을 떠올려보면 좋을 거 같다.