[leetcode] Count Subarrays With Fixed Bounds

문제

• 문제 링크
• 배열 nums와 두 정수 minK, maxK가 주어진다. nums의 subarray 중에서 최대값이 maxK이고 최소값이 minK인 subarray 개수를 구해야 한다.
• 제약 조건
  • 배열 길이: 2 <= nums.length <= 10^5
  • 배열 값과 minK, maxK 범위: 1 <= nums[i], minK, maxK <= 10^6

풀이

풀기 전

• 아이디어 생각하는 데에 오래 걸렸다. 난이도가 hard로 되어 있어서 더 겁먹은 거 같다. 예시를 이리저리 생각해보며 어떻게 풀면 좋을지 고민했다.
• 그 동안 조건이 달린 subarray 문제를 풀면서 알게 된 건, 특정 상태를 전제하고 풀면 수월하다는 거다.
  • 첫 번째는 배열을 순회할 때, 현재 순회하고 있는 값까지만 조건을 체크한다. 뒤에 순회하게 되는 값까지 생각하면 너무 복잡해진다. 중복되는 건 나중에 생각하고 계산해준다.
  • 두 번째는 조건을 만족하는 가장 작은 subarray를 구한 뒤, 이 subarray를 기준으로 해서 다른 subarray를 찾아가면 쉽다는 거다. 그러면 규칙을 발견하기가 쉬워지는 걸 느꼈다.
• 해당 문제도 위의 생각을 거쳐서 풀이를 떠올렸다. 일단 현재 탐색하고 있는 값에서 조건을 만족하는 가장 작은 subarray를 구한 뒤 정답을 어떻게 찾아갈지 고민했다. 그래서 아래와 같은 규칙을 발견했다.
  • ex) nums = [2, 1, 1, 5, 1, 7], minK = 1, maxK = 5
    • (1) idx = 0
      • nums[0]는 2이다.
      • minK와 maxK 모두 만족하지 못한다. 하지만 조건 안에 포함될 수 있는 값이다.
    • (2) idx = 1
      • nums[1]는 1이다.
      • minK만을 만족한다.
    • (3) idx = 2
      • nums[2]는 1이다.
      • minK만을 만족한다.
    • (4) idx = 3
      • nums[3]은 5다.
      • maxK를 만족한다. 그리고 현재 nums[3]까지 오면서 minK도 만족하고 있다.
      • 조건을 만족하는 가장 작은 subarray는 nums[2] ~ nums[3]이다. 그리고 조건을 만족하는 가장 큰 subarray는 nums[0] ~ nums[3]이다. 해당 범위에서 조건을 만족하는 subarray 개수는 (작은 subarray 시작 인덱스) - (큰 subarray 시작 인덱스) + 1 = 2 - 0 + 1 = 3으로 구할 수 있다. 말로 설명하면 [2, 1, 1, 5] 안에서 [1, 5]를 포함하는 subarray 개수라고 할 수 있다.
    • (5) idx = 4
      • nums[4]는 1이다.
      • minK를 만족한다. 그리고 현재 nums[4]까지 오면서 maxK도 만족하고 있다.
      • 조건을 만족하는 가장 작은 subarray는 nums[3] ~ nums[4]이다. 가장 큰 subarray는 nums[0] ~ nums[3]이다. 동일하게 조건을 만족하는 subarray 개수 계산해주면 3 - 0 + 1 = 4다.
    • (6) idx = 5
      • nums[5]는 7이다.
      • maxK보다 크다! 그래서 해당 값은 조건 안에 포함될 수 없다. 해당 값 이후부터 다시 조건을 체크해나가야 한다.
    • (7) 끝
      • 배열을 모두 순회해서 종료한다. 조건을 만족하는 총 subarray 개수는 7개다.

코드

class Solution {
    public long countSubarrays(int[] nums, int minK, int maxK) {
        long ans = 0;

        int num;
        int minIdx = 0, maxIdx = 0;  // 각각 minK와 maxK를 만났을 때의 인덱스 값이다.
        int lastMeetIdx = 0;  // 조건을 만족하는 가장 큰 인덱스를 찾기 위해 사용한다.
        boolean meetMin = false, meetMax = false;  // minK와 maxK를 만족했는지 나타낸다.
        for (int i=0; i<nums.length; i++) {
            num = nums[i];
            
            // 만약 minK와 같은 값을 만나면 인덱스와 만족 여부를 갱신한다.
            if (num == minK) {
                minIdx = i;
                meetMin = true;
            }
            // 만약 maxK와 같은 값을 만나면 인덱스와 만족 여부를 갱신한다.
            if (num == maxK) {
                maxIdx = i;
                meetMax = true;
            }

			// 조건을 벗어난 값을 만나면 조건 만족 여부를 false로 바꾼다.
            // 조건을 만족하는 가장 큰 인덱스 값도 다음 인덱스로 설정한다.
            if (num < minK || num > maxK) {
                meetMin = false;
                meetMax = false;
                lastMeetIdx = i + 1;
            }

			// 현재 위치에서 minK와 maxK를 모두 만족하면,
            // 조건을 만족하는 subarray 개수를 정답에 추가한다.
            if (meetMin && meetMax)
                ans += Math.min(minIdx, maxIdx) - lastMeetIdx + 1;
        }
        return ans;
    }
}

푼 후

• 반환 타입부터가 long이고 배열 길이도 최대 10^5여서 모든 경우의 수를 살필 수는 없겠다 생각했다.
• 다른 사람 코드를 볼까.. 하다가 끝까지 풀어봤는데 잘 풀려서 다행이다. 나중에 다른 사람 코드도 확인해봤는데 다들 비슷하게 풀었다.