[Leet Code] Number of Subarrays with Bounded Maximum

안녕하세요. 오늘은 6월 3주차 3번째 알고리즘인 Number of Subarrays with Bounded Maximum 풀이를 작성해보겠습니다!

---

문제

요약
주어진 nums 배열의 부분 배열 중에서 부분 배열의 max 값이 left <= max <= right 인 부분 배열의 개수를 구해 return 하는 문제입니다.

처음으로 생각한 방법

2중 for문을 순회하면서 부분 배열을 구하는 방법을 생각했습니다.
nums 배열 중에서 left <= nums[i] <= right 인 값이 들어오면 부분 배열을 구하는 방식이었습니다.

하지만, 유효한 부분 배열의 기준이 max 값이라는 것을 간과했습니다.
부분 배열의 첫 요소가 꼭 left 와 right 의 사이값이 아니어도 max 값만 left 와 right 의 사이값이면 되는 것이었습니다.

두번째로 생각한 방법

여전히 2중 for문을 활용합니다.
nums 배열 중에서 right 보다 큰 값이 들어왔을 때만 continue 처리합니다.
그리고 처음 들어온 요소가 left 와 right 의 사이값이라면 result 를 1 더해줍니다.
그 후로 두번째 for문을 순회하면서 부분 배열을 구합니다.
결과는 Accept!

아래부터 코드 설명에 들어가겠습니다.

---

코드 설명

int result = 0;

결과를 return 할 result 변수를 0으로 초기화합니다.

for (int i = 0; i < nums.length; i++) {
    if (nums[i] > right) continue;
    else if (nums[i] <= right && nums[i] >= left) result++;

	// ...
}

바로 for 문을 순회합니다.
nums[i] 가 right 보다 크다면 부분 배열을 만들 수 없으므로 continue 처리를 해줍니다.
만약 nums[i] 가 left 와 right 의 사이값이라면 그 자체로도 부분 배열이 성립하므로 result 를 1 더해줍니다.

for (int i = 0; i < nums.length; i++) {
    // ...
    
    int max = nums[i];

    // ...
}

그 다음 max 를 nums[i] 로 설정한 후에 두번째 for문을 순회합니다.

for (int i = 0; i < nums.length; i++) {
    // ...
    
    for (int j = i + 1; j < nums.length; j++) {
        if (nums[j] > right) break;
        if (max < nums[j]) max = nums[j];

        if (max <= right && max >= left) result++;
    }
}

두번째 for문은 i 다음 인덱스부터 차례로 체크합니다.
만약 nums[j] 가 right 보다 크다면, 그 이후터 부분 배열이 성립하지 않으므로 break 를 설정해 for문을 빠져나옵니다.
nums[j] 가 right 보다 크지 않고, max 보다 크다면 max 값을 바꿔줍니다.

현재 max 가 left 와 right 의 사이값이라면 result 를 1 더해줍니다.
이것을 체크하는 이유는 여전히 max 가 left 보다 작을 경우도 있기 때문입니다.

전체 코드

class Solution {
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        int result = 0;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > right) continue;
            else if (nums[i] <= right && nums[i] >= left) result++;

            int max = nums[i];

            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] > right) break;
                if (max < nums[j]) max = nums[j];

                if (max <= right && max >= left) result++;
            }
        }

        return result;
    }
}

---

마무리

오늘도.. 제가 문제를 제대로 이해하지도 않고 무작정 알고리즘을 푼다는 것을 체감했습니다.
이 단점 고쳐야하는데 성격이 급한게 문제인건지 잘 고쳐지지 않네요.. ㅜ.ㅜ

아무튼! 이번 포스팅도 읽어주셔서 감사합니다 :)