Sum of Subarray Minimums

https://leetcode.com/problems/sum-of-subarray-minimums/

Sum of Subarray Minimums - LeetCode

문제는 주어진 array 의 모든 sub array에 대해서 최소값을 구해서 합계를 내는 것이다

처음에는 난이도가 Medium이지만 무식하게 짜보았다

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        result = 0
        # sub array len        
        for sal in range(1, len(arr) + 1):
            for index in list(range(0, len(arr) - sal + 1)):
                sub_arr = arr[index:index+sal]
                result = result + min(sub_arr)
                
        return result

모든 sub array를 직접 만들고 최소값을 구해서 더했다
결과는 당연히~

대부분 알고리즘 문제가 시간복잡도니깐...
대충 생각하면 sub array를 만드는건 O(n^2)이고 python에서 제공하는 min 함수는 O(nlogn) 정도일테니
대략 지금 작성한 코드는 O(n^3 * logn) 정도일테니 당연한 결과이다 ㅎ

그래서 2번째 방식으로는 dynamic programming 을 적용해서
min을 안쓰고 구하는 방식을 적용해봤다
단순하게 길이가 1개인 sub array의 최소값 결과부터 저장해서 그걸 다음에서도 활용하는 것이다

arr = [3,1,2,4] 일때
[3,1] => 최소값 1
[3,1,2] => [3,1]의 최소값은 1이니깐 1과 추가된 2만 비교
[3,1,2,4] => [3,1,2]의 최소값은 1이니깐 1과 추가된 4만 비교

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        result = 0
        before_min_lists = []
        current_min_lists = []
        
        # sub array len        
        for sal in range(1, len(arr) + 1):
            current_min_lists = []
            for index in list(range(0, len(arr) - sal + 1)):
                # sub_arr = arr[index:index+sal]
                min_value = 0
                if sal == 1:
                    min_value = arr[index]
                elif arr[index+sal-1] < before_min_lists[index]:
                    min_value = arr[index+sal-1]
                else: 
                    min_value = before_min_lists[index]
                result = result + min_value
                current_min_lists.append(min_value)
            before_min_lists = current_min_lists
                
        return result % (10 ** 9 + 7)

이러면 O(nlogn) => O(n) 으로 줄어들테니 좀 더 빨라지지 않을까...?
대충 눈코딩은 맞는듯하여 제출해보았다

하...

이러면 앞에 sub array 조차도 최소한 O(n^2) => O(nlogn)으로 줄이라는건데
결국 그래봤자 O(n^2 * logn)이다

느낌상 O(n^2) 이하로 구현을 해야되는것 같은데 아무리 생각해봐도 답이 나오질 않는다.. ㅋㅋㅋㅋ

힌트를 참고해볼까하고 Related Topics를 봤는데 아래와 같다

근데 이걸 봐도 Monotonic Stack을 활용할 방안은 떠오르지 않았다

Monotonic Stack은 가지고 있는 원소를 오름차순(or 내림차순)을 유지하는 스택인데
이미 위에서 내가 Dynamic Progaramming 을 통해서 최소값 찾는 시간복잡도를 줄였고
내가 생각할 수 있는 방식들은 결국 모든 sub array를 순회해야 모든 최소값을 찾을 수 있는 구조라
여기서부터는 내가 모르는 알고리즘 기법(또는 수학)이 있는듯하여 고민을 멈추고 Discuss 에 있는 답을 보았다

class Solution:
    def sumSubarrayMins(self, A):
        res = 0
        stack = []  #  non-decreasing 
        A = [float('-inf')] + A + [float('-inf')]
        for i, n in enumerate(A):
            while stack and A[stack[-1]] > n:
                cur = stack.pop()
                res += A[cur] * (i - cur) * (cur - stack[-1]) 
            stack.append(i)
        return res % (10**9 + 7)

처음에 딱보고 든 생각은 "이게 뭐시여"였고
코드를 보고 나니 약간 수학적인 아이디어가 필요한 부분이었다

난 계속 모든 sub array를 참조해서 최소값을 구할 생각을 했는데
최소값에 대해서 boundary를 구해서 그걸 활용한다는것이다

[3,1,2,4]가 있으면
최소값이 3인 boundary는 [3]
최소값이 1인 boundary는 [3,1,2,4]
최소값이 2인 boundary는 [2, 4]
최소값이 4인 boundary는 [4]

그렇다면 n이 최소값될 sub array의 수는 (left boundary - indexof(n)) * (right boundary - indexof(n)) 이다

이러면 매번 최소값을 구할 필요도 없고 모든 sub array를 순회할 필요도 없다

주어진 array의 모든 원소만 순회하면서 원소가 최소값인 left/right boundary만 구하면 된다

결국 O(nlogn)으로 구해지는 문제였다

이게 보니깐 이해는 가는데 참... 아직 많이 멀었다는 생각이 드는 문제였다 ㅎ...

아직까진 코테에서 이런 씽크빅한 문제는 만나질 못했는데 이런 알고리즘만 전문적으로 준비하는 사람들보면 여러모로 대단한듯하다