[LeetCode][JAVA] 907. Sum of Subarray Minimums

이호준·2024년 1월 22일

Java leetcode

LeetCode

목록 보기

10/11

문제링크: 907. Sum of Subarray Minimums

📖 문제설명

정수 배열이 주어졌을 때, 최소값 b의 합을 구하여라. b는 정수 배열에서 구할 수 있는 연속되는 부분배열의 최소값이다. 값이 너무 커질 것을 고려해서 10^9 + 7의 모듈러 계산을 적용한다.

💡 접근방식

굉장히 비효율 적인 것을 알지만 반복문을 3중첩 해서 완전탐색으로 부분배열을 구하고 그 안에 최소값을 찾는 방법 밖에 생각나지 않았다.

코드:

class Solution {
    final static int MODULO = 1000000007;
    final static int MIN_VALUE = 30000;
    public int sumSubarrayMins(int[] arr) {
        int sum = 0;

        for(int i=1; i<=arr.length; i++){
            for(int j=0; j<=arr.length-i; j++){
                int min = MIN_VALUE;
                for(int k=j; k<j+i; k++){
                    if(arr[k]<min) min=arr[k];
                }
                sum = (sum+min)%MODULO;
            }
        }

        return sum;
    }
}

당연히 Time Limit에 걸렸고 문제에서 요구하는 알고리즘에 부합하지 않았다.

📌 개선

문제에서 제공하는 힌트로 단조스택을 사용하여 DP방법으로 푸는 것이 이 문제의 핵심이다.

연속되는 부분배열의 의미

우선 연속되는 부분배열이란 조건을 다르게 생각하면 특정한 값을 기준으로 오른쪽 왼쪽으로 자신보다 작은 값이 나올 때 까지 샐 수 있는 개수 만큼 부분 집합을 만들 수 있다는 뜻이었다.

문제의 예시2에서 주어진 배열로 설명하면

[11,81,94,43,3]

위 배열에서 만들어 질 수 있는 부분배열은

[11][81][94][43][3]
[11,81][81,94][94,43][43,3]
[11,81,94][82,94,43][94,43,3]
[11,81,94,43][81,94,43,3]
[11,81,94,43,3]

으로 배열의 길이를 n이라 했을 때 n+(n-1)+(n-2)+...+1개의 개수가 나온다.

이때 0번째 부터 자신이 가장 작은 요소인 부분배열로 정리해서 보면

11: [11][11,81][11,81,94][11,81,94,43]
81: [81][81,94]
94: [94]
43: [81,94,43][94,43][43]
3: [11,81,94,43,3][81,94,43,3][94,43,3][43,3][3]

이렇게 정리가 된다. 위에 정리된 정보에 따르면 모든 부분배열이 앞에 적혀 있는 각 값을 기준으로 보았을 때 그 값보다 작은 값을 만나기 전까지 부분배열을 만들 수 있는 것을 볼 수 있다.

그렇다면 기준이 되는 특정값과 탐색에서 다음 값이 자신보다 작다는 것을 알 수 있어야 위와 같은 부분배열의 개수를 알 수 있게 된다. 자신이 가장 작은 값임을 확신하는 부분배열의 개수를 확인하면 부분배열의 개수*값을 모든 값에서 반복하면서 더하면 문제에서 요구하는 해가 나오므로 해당방법을 구현하면 된다.

개선코드

코드:

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

        for (int i = 0; i <= arr.length; i++) {
            while (!st.empty() && (i == arr.length || arr[st.peek()] >= arr[i])) {
                int mid = st.pop();
                int leftBoundary = st.empty() ? -1 : st.peek();
                int rightBoundary = i;

                long count = (mid - leftBoundary) * (rightBoundary - mid) % MOD;

                sum += (count * arr[mid]) % MOD;
                sum %= MOD;
            }
            st.push(i);
        }

        return (int) sum;
    }
}