leetcode 907. Sum of Subarray Minimums

문제 요약

주어진 arr로 구성된 모든 subarray에서의 최소값들의 합을 구하는 문제였습니다.

 

해결

time limit exceed 접근법

처음에는 stack을 만들고 monotonic increasing stack을 만들고 매 index마다 stack에 들어있는 것을 꺼내어 답을 도출했습니다. 하지만 매 index마다 stack에 들어있는 것을 꺼내는 과정이 사실 이 문제는 O(n)으로 끝내야 하는 문제인데 최악의 경우 O(n^2) 케이스가 발생될 수도 있어 time limit exceed가 발생되고 말았습니다.

수학적 접근법   

따라서 이를 해결하기 위해선 수학적 접근법을 이용할 수 있는데요. 

우선 특정 범위 내에서 최소값이 정해진다고 할 때 그 수 주변에 왼쪽, 오른쪽을 고려해볼 수 있습니다.

만약 [3, 4, 5, 2, 3, 4]가 있고 최소값이 2라고 알 경우 왼쪽에 3개 + 1개(아무것도 선택하지 않은 경우), 오른쪽에 2개 + 1개(아무것도 선택하지 않은 경우)여서 총 이 경우 부분집합은 4 * 3개가 되고 최소값의 합은 12(개수) * 2(최소값)이어서 24가 되게 됩니다.

이렇게 되면 사실 최소값만 알 경우 일일이 다시 꺼내보지 않더라도 O(1)로 부분집합의 합을 구할 수 있습니다.

그렇다면 이제 최소값을 어떻게 구할지 인데요. 이것은 monotonic increasing stack 으로 stack을 구성하여 최소값을 그때그때 구해서 합쳐 나갑니다. 

class Solution {
    public int sumSubarrayMins(int[] arr) {
        Stack<Integer> stack = new Stack<>();
        long answer = 0;
        int MOD = 1000000007;

        for(int i = 0; i <= arr.length; i++) {
            while(!stack.empty() && (i == arr.length || arr[stack.peek()] >= arr[i])) {
                int mid = stack.pop();
                int nextSmaller = i;
                int prevSmaller = stack.isEmpty() ? -1 : stack.peek();  // 인덱스 도출
                // 경우의 수, 우측 * 좌측, 없는 경우의 수 고려하여 양쪽 +1 더해짐
                long count = (nextSmaller - mid) * (mid - prevSmaller) % MOD;
                answer += arr[mid] * count;
                answer %= MOD;
            }
            stack.push(i);
        }
    	return (int)answer % MOD;
	}
}

여기서 살펴볼 디테일한 부분은 prevSmaller에서 -1 설정 조건을 둔거랑 arr.length까지 인덱스 고려하여 '아무것도 선택하지 않은 경우'도 반영되었다는 점과 while 조건을 통해 최소값이 만족되는 모든 subarray에 대해서 빠짐없이 합쳐지고 있다는 점입니다.

 

교훈

어떻게 보면 초기에 제가 time limit exceed의 접근법과 비슷하긴 한데요. 그치만 매번 모두 다 꺼내는 것이 아니라 그 케이스에 속하는 것 모두를 한번에 처리하고 그 과정에서 수학적으로 접근한다는 점에서는 차이가 있습니다.

문제 안에 여러 장치들이 작동되어 문제가 해결되고 있습니다. Medium문제이긴 하였지만 사실 Hard 문제의 체감이 느껴졌습니다.