Number of Subarrays with Bounded Maximum

문제 링크 : https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/

Number of Subarrays with Bounded Maximum - LeetCode

문제 해설 : 양수가 저장된 배열 nums와 두 양수 left, right가 주어집니다. ( left <= right)

nums의 subarray(연속적이며 비어있지 않음) 중 원소의 최대값이 left 이상 right 이하를 만족하는 경우의 수를 반환하세요.

 

제한 사항

1) left, right와 nums[i]는 [0, 10^9] 범위를 만족합니다.

2) nums의 길이는 [1, 50000]을 만족합니다.

 

 

모든 경우를 탐색하는 완전 탐색을 구현하여 문제를 해결했습니다.

from typing import List

class Solution:
    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
        answer = 0
        for start in range(len(nums)):
            maximum = nums[start]
            for end in range(start, len(nums)):
                maximum = max(maximum, nums[end])
                if maximum > right:
                    break
                elif maximum < left:
                    continue
                answer += 1
        return answer

 

start는 subarray의 왼쪽 끝, end는 subarray의 오른쪽 끝입니다.

maximum은 start와 end 사이의 원소 중 최대값입니다.

maximum이 right보다 크면 더 이상 뒤를 탐색할 필요가 없으므로 반복문을 종료하였습니다.

 

 

문제는 정답처리되었지만 코드 자체는 개선할 여지가 있습니다.

nums의 길이가 최대 50000이므로 모든 경우를 탐색하면 최악의 경우엔 약 25 억번 반복문이 실행되어

시간 초과 판정을 받을 수 있습니다. 해당 문제를 좀 더 효율적인 알고리즘으로 풀기 위해 다른 방법을 시도해봐야 할 것 같습니다.