문제 이해하기
배열 nums가 주어졌을 때, 비어 있지 않은 모든 부분 배열(subarray) 중에서 최소 곱(min-product)이 가장 큰 값을 찾아야 합니다. 결과값이 매우 커질 수 있으므로 10^9+7로 나눈 나머지를 반환합니다.
여기서 '최소 곱'이란 배열 안의 최솟값 × 배열 전체의 합을 의미합니다. 예를 들어 배열이 [4, 3, 6]이라면 최솟값은 3이고, 최소 곱은 다음과 같이 계산됩니다.
3 × (4 + 3 + 6) = 3 × 13 = 39
입력 예시
nums = [2, 3, 4, 3]이 주어진 경우 출력은 30입니다. 부분 배열 [3, 4, 3]을 선택했을 때 결과가 최대가 되며, 계산 과정은 다음과 같습니다.
3 × (3 + 4 + 3) = 3 × 10 = 30
해결 접근 방법
이 문제는 단조 스택(Monotonic Stack) 기법을 활용하면 효율적으로 풀 수 있습니다. 배열을 한 번만 순회하면서 스택을 관리하고, 현재 값보다 크거나 같은 요소들이 스택에서 빠져나갈 때마다 그 요소를 최솟값으로 하는 부분 배열의 최소 곱을 계산합니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- m := 10^9 + 7 (모듈로 연산에 사용할 값)
- stack := 새로운 스택 생성
- rsum := 0, res := 0 (누적 합과 결과값 초기화)
- nums의 끝에 0을 추가 → 스택을 마지막까지 비우기 위한 센티널(sentinel) 역할
- nums의 각 인덱스 i와 값 v에 대해 반복:
- 스택이 비어 있지 않고, 스택 맨 위 인덱스의 값이 v보다 크거나 같은 동안:
- 스택에서 top을 꺼낸다 (index, val)
- arrSum := rsum
- 스택이 비어 있지 않다면 arrSum := rsum − 스택 top의 누적합 값
- res := res와 (nums[index] × arrSum) 중 더 큰 값
- rsum := rsum + v
- 스택에 (i, rsum)을 push
- 스택이 비어 있지 않고, 스택 맨 위 인덱스의 값이 v보다 크거나 같은 동안:
- res mod m 반환
파이썬 코드 구현
아래 코드를 통해 동작 방식을 더 잘 이해할 수 있습니다.
def solve(nums):
m = int(1e9+7)
stack = []
rsum = 0
res = 0
nums.append(0)
for i, v in enumerate(nums):
while stack and nums[stack[-1][0]] >= v:
index, _ = stack.pop()
arrSum = rsum
if stack:
arrSum = rsum - stack[-1][1]
res = max(res, nums[index]*arrSum)
rsum += v
stack.append((i, rsum))
return res % m
nums = [2,3,4,3]
print(solve(nums))입력
[2,3,4,3]
출력
30
마무리
이 알고리즘은 각 요소가 스택에 최대 한 번씩 push되고 pop되므로 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)입니다. 브루트 포스 방식으로 모든 부분 배열을 탐색하는 O(n²) 이상의 방법보다 훨씬 효율적이며, 배열의 크기가 클 때도 안정적으로 동작합니다.