[2024] Day19. 907. Sum of Subarray Minimums

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 1월 19일 (금)
Leetcode daily problem

907. Sum of Subarray Minimums

https://leetcode.com/problems/sum-of-subarray-minimums/?envType=daily-question&envId=2024-01-20

Problem

정수 배열 arr이 주어질 때, 배열 arr 내의 가능한 모든 연속 하위 배열에 대한 최소 요소의 합을 계산해야 하는 문제이다.
연속 하위 배열은 간격 없이 연속되는 배열 요소의 시퀀스이다.
예를 들어, [3, 1, 2, 4] 배열에서 [1, 2, 4]는 연속된 하위 배열이지만 [3, 2]는 연속된 하위 배열이 아니다.
[3,1,2,4] 배열의 하위 배열은 [3], [1], [2], [4], [3,1], [3,1,2], [3,1,2,4], [1,2]... 등이다.

숫자가 너무 크다면 결과값은 10^9 + 7로 반환한다.

Solution

동적 프로그래밍(Dynamic Programming)

이 문제를 해결하기 위해서는 배열의 각 요소가 일부 하위 배열 수에서 최소값이 된다는 점을 생각해야 한다. 문제를 풀기 위해 모든 하위 배열을 고려하면 시간복잡도가 늘어나고 비효율적이게 된다.

효율적으로 문제를 해결하기 위해서는 각 요소 arr[i]에 대해 두 가지를 탐색하는데,

left[i]: arr[i] 왼쪽에 있는 첫 번째 작은 요소의 인덱스
right[i]: arr[i] 오른쪽의 arr[i] 보다 작거나 같은 첫 번째 요소의 인덱스

left[i] 및 right[i]가 결정되면 arr[i]가 최소인 하위 배열의 수는
(i - left[i]) * (right[i] - i)로 계산할 수 있다.

특정 하위 배열을 중복 계산을 방지하기 위해서 arr[i]보다 작거나 같은 오른쪽의 첫 번째 요소를 찾고 있는데, 왼쪽 및 오른쪽 인덱스를 유지하기 위해 요소를 증가 또는 감소 순서로 유지하는 스택을 사용한다.
해당 스택은 두 번의 탐색 과정을 거치게 되는데 한 번은 왼쪽에서 오른쪽으로 이동하여 각 left[i]를 찾고, 오른쪽에서 왼쪽으로 한 번은 각 right[i]를 찾는 과정이다.
스택의 각 요소는 아직 발견되지 않았거나 처리되지 않은 요소에 대해 다음으로 큰 요소를 나타냅니다.

(i - left[i])와 (right[i] - i)의 곱은 arr[i]가 최소값인 하위 배열의 개수를 제공하고, 그런 다음 이 개수에 arr[i]를 곱하여 arr[i]가 포함된 횟수를 계산한다.
모든 요소가 포함된 값을 합산하고 해당 값이 너무 크다면 10^9 + 7을 반환한다.

Code

Complexicity

시간 복잡도

공간 복잡도

---