문제 개요
숫자로 구성된 목록 nums와 인덱스 값 pos가 주어졌을 때, 인덱스 pos를 반드시 포함하는 연속된 부분 리스트 A를 찾아 (A의 최솟값) × (A의 크기)가 최대가 되는 값을 구해 반환해야 합니다.
예를 들어 입력이 nums = [-2, 2, 5, 4], pos = 3이라면 결과는 8입니다. 가장 좋은 부분 리스트는 [5, 4]이며, 최솟값은 4, 크기는 2이므로 4 × 2 = 8이 되기 때문입니다.
접근 방법: 탐욕(Greedy) 알고리즘
이 문제는 탐욕 기법으로 효율적으로 해결할 수 있습니다. 시작 지점 pos에서 출발해 왼쪽 또는 오른쪽으로 한 칸씩 구간을 확장하되, 항상 더 큰 값을 가진 방향으로 확장하는 것이 핵심입니다. 이렇게 하면 각 확장 단계에서 구간의 최솟값이 가능한 한 크게 유지됩니다.
구체적인 절차는 다음과 같습니다:
ans := A[pos],m := A[pos]로 초기화합니다.i := pos,j := pos로 초기화합니다. (i는 왼쪽 경계, j는 오른쪽 경계)(A의 크기 − 1)번 동안 다음을 반복합니다:
left: i − 1 ≥ 0이면 A[i − 1], 그렇지 않으면 −∞right: j + 1 < A의 크기이면 A[j + 1], 그렇지 않으면 −∞left ≥ right라면 왼쪽으로 확장합니다. i를 1 감소시키고, m을 m과 A[i] 중 최솟값으로 갱신합니다.
그렇지 않으면 오른쪽으로 확장합니다. j를 1 증가시키고, m을 m과 A[j] 중 최솟값으로 갱신합니다.
ans를 ans와 (m × (j − i + 1)) 중 최댓값으로 갱신합니다.
반복이 끝나면 ans를 반환합니다.
예제 코드
다음 구현을 통해 더 자세히 이해해 보겠습니다:
class Solution:
def solve(self, A, pos):
NINF = float("-inf")
ans = m = A[pos]
i = pos
j = pos
for _ in range(len(A) - 1):
left = A[i - 1] if i - 1 >= 0 else NINF
right = A[j + 1] if j + 1 < len(A) else NINF
if left >= right:
i -= 1
m = min(m, A[i])
else:
j += 1
m = min(m, A[j])
ans = max(ans, m * (j - i + 1))
return ans
ob = Solution()
nums = [-2, 2, 5, 4]
pos = 3
print(ob.solve(nums, pos))
입력
[-2, 2, 5, 4], 3
출력
8
동작 과정 단계별 살펴보기
위 예제에서 알고리즘이 실제로 어떻게 진행되는지 확인해 보겠습니다:
초기 상태 : i = j = 3, 구간은 [4] 하나입니다. m = 4, ans = 4
1단계 : 왼쪽 값 5와 오른쪽 값(−∞)을 비교하면 왼쪽이 더 크므로 왼쪽으로 확장합니다. 구간은 [5, 4]가 되고, m = 4, ans = max(4, 4 × 2) = 8
2단계 : 왼쪽 값 2로 확장하면 구간은 [2, 5, 4], m = 2, ans = max(8, 2 × 3) = 8 (변화 없음)
3단계 : 마지막으로 왼쪽 값 −2까지 확장하면 구간은 전체 [-2, 2, 5, 4], m = −2, ans = max(8, −2 × 4) = 8
최종 답은 8이 됩니다.
복잡도 분석
이 알고리즘은 배열의 각 요소를 정확히 한 번씩만 방문하므로 시간 복잡도는 O(n)이며, 추가 메모리를 거의 사용하지 않으므로 공간 복잡도는 O(1)입니다. 모든 가능한 부분 리스트를 일일이 검사하는 브루트포스 방식(O(n²))에 비해 훨씬 효율적입니다.