leetcode 2444. Count Subarrays With Fixed Bounds

문제 요약

minK, maxK를 만족하는 subarray가 몇 개가 있는지를 구하는 문제였습니다.

 

해결

문제는 간단했지만 subarray를 어떻게 나눌 것인지가 쉽지 않았습니다.

O(n)으로 해결해야 하는 이런 문제의 경우 대부분의 케이스에 subarray를 나누는 것이 아닌 다른 접근법을 생각해야하는데 사실 그게 쉽게 떠오르지 않았고 결국 다른 사람의 답안을 참고하였습니다.

문제에서 포인터를 2개를 두어 해결하였습니다. minPos, maxPos라는 각각의 포인터는 문제의 요구사항을 충족하는 subarray의 index를 들고 있었고 그런 케이스가 없는 경우 -1이 갱신되지 않아 제대로 반영되지 않습니다.

2개의 포인터 외에 leftBound 변수가 있는데 이 값은 유효한 subarray의 개수를 셀 때 이용됩니다. 예를들어 유효한 [1, 3, 5]가 있고 maxPos=2, minPos=0, leftBound가 초기화 값인 -1인 경우 Math.min(minPos, maxPos) - leftBound는 2 - (-1)로 3개가 딱 나오게 됩니다. 만약 minK보다 작거나 maxK보다 크게 되면 subarray가 더이상 유효하지 않은 것으로 보고 leftBound가 업데이트 됩니다.

class Solution {
    public long countSubarrays(int[] nums, int minK, int maxK) {
        long answer = 0;
        int minPos = -1, maxPos = -1, leftBound = -1;
        for(int i = 0; i < nums.length; i++) {
        	// 기존 subarray 유효하지 않아 기준점 변경
            if(nums[i] < minK || nums[i] > maxK) {
                leftBound = i;
            }

            if(nums[i] == minK) {
                minPos = i;
            }
            if(nums[i] == maxK) {
                maxPos = i;
            }
            answer += Math.max(0, Math.min(minPos, maxPos) - leftBound);
        }   
        return answer; 
    }
}

 

교훈

Sliding Window의 문제의 경우 우선 포인터를 2개 쓰는 접근법도 같이 연상해서 생각해보면 좋을 것 같습니다.

Monotonic Queue의 연습문제로 풀려고 했는데 사실 그 개념이 딱 들어맞는것처럼 보이진 않습니다.