파이썬으로 좋은 하위 배열(Good Subarray)의 최대 점수 찾는 프로그램

문제 설명

배열 nums와 값 k가 주어집니다. 이때 하위 배열(subarray) (i, j)의 점수는 다음과 같이 정의됩니다.

score(i, j) = min(nums[i..j]) × (j − i + 1)

여기서 "좋은(good) 하위 배열"은 시작 인덱스와 끝 인덱스 사이에 k가 포함되는, 즉 i <= k <= j를 만족하는 하위 배열을 뜻합니다. 목표는 좋은 하위 배열 중에서 얻을 수 있는 최대 점수를 구하는 것입니다.

예시

입력이 nums = [2,5,4,8,5,6], k = 3인 경우를 살펴보겠습니다. 최적의 하위 배열은 (1, 5)이며, nums[1..5] 구간의 최솟값은 4이고 구간의 길이는 5이므로 점수는 4 × (5 − 1 + 1) = 20이 됩니다.

접근 방법: 투 포인터(Two Pointer)

이 문제는 인덱스 k를 기준으로 왼쪽과 오른쪽으로 동시에 확장해 나가는 투 포인터 기법으로 효율적으로 해결할 수 있습니다. 현재까지 탐색한 구간의 최솟값(minNum)을 추적하면서, 구간을 확장할 때마다 좌우 후보 값 중 더 큰 쪽으로 최솟값을 갱신하고 그에 따른 점수를 계산합니다.

알고리즘 단계

• ans := nums[k], minNum := nums[k]로 초기화합니다.

• 두 포인터를 i := k, j := k로 설정합니다.

• i > -1 또는 j < len(nums)인 동안 아래 과정을 반복합니다.

• 왼쪽 확장: nums[i] >= minNum인 동안 i -= 1을 수행합니다.

• 오른쪽 확장: nums[j] >= minNum인 동안 j += 1을 수행합니다.

• ans := max(ans, (j - i - 1) * minNum)으로 정답을 갱신합니다.

• 왼쪽 값(nums[i])과 오른쪽 값(nums[j]) 중 더 큰 값을 새로운 minNum으로 설정하며, 포인터가 범위를 벗어난 경우에는 -1을 사용합니다.

• 반복이 종료되면 ans를 반환합니다.

파이썬 구현 코드

다음 구현 예제를 통해 더 자세히 이해해 보겠습니다.

def solve(nums, k):
    ans = nums[k]
    minNum = nums[k]
    i = k
    j = k
    while i > -1 or j < len(nums):
        while i > -1 and nums[i] >= minNum:
            i -= 1
        while j < len(nums) and nums[j] >= minNum:
            j += 1
        ans = max(ans, (j - i - 1) * minNum)
        minNum = max(nums[i] if i > -1 else -1, nums[j] if j <
len(nums) else -1)
    return ans

nums = [2,5,4,8,5,6]
k = 3
print(solve(nums, k))

입력

[2,5,4,8,5,6], 3

출력

20