Leetcode - 907. Sum of Subarray Minimums
문제 개요
한 정수 배열 arr이 주어진다. 이 때 arr의 subarray들 내의 최소 값들의 합을 구해야 한다.
이때, 각 subarray들의 수는 순차적이어야 한다.
예를 들어, arr = [3,1,2,4]일 경우 subarray는 아래와 같다.
subarray:
[3], [1], [2], [4]
[3, 1], [3, 2], [3, 4], [1, 2], [1, 4], [2, 4]
[3, 1, 2], [3, 1, 4], [1, 2, 4]
[3, 1, 2, 4]
subarray들은 arr내 순차적으로 쌓여야 하므로 1을 건너뛴 [3,2]나, [1,4]등은 제외 해야 한다.
따라서, 최종 subarray는 아래와 같다
각 subarray들 내의 최소 값은 아래와 같이 나타나며 결과 값은 17이다.
subarray 들의 최소값들
규칙 찾기
시작 idx에 따라 subarray를 찾게되면 아래와 같은 규칙이 나오게 된다.
[3] = 3
[3, 1] = 1
[3, 1, 2] = 1
[3, 1, 2, 4] = 1
[1] = 1
[1, 2] = 1
[1, 2, 4] = 1
[2] = 2
[2, 4] = 2
[4] = 4
class Solution:
def sumSubarrayMins(self, arr: List[int]) -> int:
result = [0] * len(arr)
min_value = float('inf')
for idx in range(len(arr) - 1, -1, -1):
min_value = min(min_value, arr[idx])
# 현재 arr값을 제외한 나머지 값의 최소값은 min_value
# idx = 3, arr[idx] = 4 0 (idx)
result[idx] = arr[idx] + (len(arr) - idx - 1) * min_value
return sum(result)
하지만, 위의 내용은 [3, 1, 2, 4]만 해당되는 내용이며, 1이 우연히 arr[1]에 있기 때문에 해당 알고리즘은 arr[1]이 최소값일 경우에만 해당된다. 다른 방법을 찾아야 한다.
두 번째 예제인 arr = [11,81,94,43,3]에 눈을 돌릴 때가 됬다. sequencearr과 최소값은 아래와 같다.
sequencearr:
11 = 11
11, 81 = 11
11, 81, 94, = 11
11, 81, 94, 43 = 11
11, 81, 94, 43, 3 = 3
81 = 81
81, 94 = 81
81, 94, 43 = 43
81, 94, 43, 3 = 3
94 = 94
94, 43 = 43
94, 43, 3 = 3
43 = 43
43, 3 = 3
3 = 3
이전 테스트 케이스는 역으로 계산했을 때, 각 idx가 최소값이었다.(첫 item인 3제외)
그러나, 이번 테스트 케이스에서는 idx = 0 일 때와 idx = 1일 때 기존 방식으로 계산할 경우, 이전 계산 값이 변경이 되어서(idx는 4부터 시작) 사용할 수 없게 되었다. 즉, 다른 규칙이 없나 살펴봐야 한다.
idx가 4, 3, 2, 1, 0순으로 접근하였을 때 아래의 그림과 같이 변경되는 시점의 순서를 알 수 있을 것이다.
[그림1]을 보면 현재 idx를 굵게 표시를 하였다. 그리고, 검은색 레이블 표시가 된 숫자는, idx와 arr[idx]인데 idx의 규칙은 아래와 같다.
해결 전략
그림 1 에서는 monotonic stack을 이용했다. monotonic stack은 아래와 같은 특징이 있다.
1. 점점 증가하거나 점점 감소하는 형태로 arr내의 자료를 저장한다.
2. 현재 넣으려고 하는 item이 stack의 top에 들어있는 item보다 작을경우, top 있는 자료를 삭제하고 넣는다.
알고리즘의 일관성을 유지시키기 위해 덧샘의 항등원인 0을 각 arr, stack, result에 추가하였다.
class Solution
def sumSubarrayMins_reverse(self, arr: List[int]) -> int:
arr = arr + [0]
result = [0] * len(arr)
stack = [len(arr) - 1] # append last idx
# iterate reverse order
for current_idx in range(len(arr) - 1, -1, -1):
while arr[stack[-1]] > arr[current_idx]:
stack.pop()
before_idx = stack[-1]
result[current_idx] = arr[current_idx] * (before_idx - current_idx) + result[before_idx]
stack.append(current_idx)
return sum(result) % (10 ** 9 + 7)
회고
문제의 난이도가 medium이었지만 개인적으로 monotonic stack을 사용해야 한다는 점과, dynamic programming의 결과 값을 일정한 규칙대로 변경하는 부분에서 어려웠다.
특히 stack에 저장해야 하는 값이 item이 아닌 인덱스 값을 저장함으로써, arr에 있는 값에 접근할 수 있는 뿐만 아니라 각 idx의 차이를 계산하는 것이 인상적이였다.
two pointer, monotonic stack, dynamic programming을 응용한 내용으로 굉장히 힘든 문제였다.