파이썬으로 가장 긴 '증가 후 감소' 부분 리스트의 길이 찾는 방법

숫자로 이루어진 리스트 nums가 주어졌을 때, 값이 먼저 엄격하게 증가한 후 엄격하게 감소하는(산 모양) 가장 긴 부분 리스트의 길이를 찾아야 합니다. 이때 부분 리스트의 최소 길이는 3 이상이어야 합니다.

예를 들어, 입력이 nums = [8, 2, 4, 6, 3, 1]이라면 출력은 5가 됩니다. 부분 리스트 [2, 4, 6, 3, 1]이 2 → 4 → 6으로 엄격하게 증가한 뒤 6 → 3 → 1로 엄격하게 감소하기 때문입니다.

해결 알고리즘

이 문제는 리스트를 한 번만 순회하면서 증가 구간과 감소 구간의 길이를 각각 세는 방식으로 해결할 수 있습니다. 구체적인 단계는 다음과 같습니다.

i := 0, n := 리스트 a의 크기, res := 음의 무한대(-inf)로 초기화합니다.
i < n - 2인 동안 다음을 반복합니다.
- st := i (현재 구간의 시작 인덱스 저장)
- linc := 0, ldec := 0 (증가 구간 길이, 감소 구간 길이 카운터)
- a[i] < a[i + 1]인 동안 linc를 1씩 늘리고 i를 전진시켜 증가 구간을 셉니다.
- a[i] > a[i + 1]인 동안 ldec를 1씩 늘리고 i를 전진시켜 감소 구간을 셉니다.
- linc > 0이고 ldec > 0이라면, 실제로 '증가 후 감소' 패턴이 존재하므로 res와 (i - st + 1) 중 더 큰 값을 res에 저장합니다.
- a[i] == a[i + 1]인 동안 i를 전진시켜 같은 값이 반복되는 구간은 건너뜁니다.
모든 순회가 끝나면 res >= 0일 때 res를, 그렇지 않으면 0을 반환합니다.

이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.

구현 예제

class Solution:
    def solve(self, a):
        i, n, res = 0, len(a), float("-inf")
        while i < n - 2:
            st = i
            linc, ldec = 0, 0
            while i < n - 1 and a[i] < a[i + 1]:
                linc += 1
                i += 1
            while i < n - 1 and a[i] > a[i + 1]:
                ldec += 1
                i += 1
            if linc > 0 and ldec > 0:
                res = max(res, i - st + 1)
            while i < n - 1 and a[i] == a[i + 1]:
                i += 1
    return res if res >= 0 else 0

ob = Solution()
nums = [8, 2, 4, 6, 3, 1]
print(ob.solve(nums))

입력

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