Python에서 가장 긴 교차 부등식 부분 리스트의 길이를 구하는 프로그램

숫자 리스트 nums가 주어졌을 때, 인접한 두 숫자 사이의 대소 관계가 항상 '작다(<)'와 '크다(>)'로 번갈아 나타나는 가장 긴 부분 리스트(sublist)의 길이를 구하는 문제입니다. 첫 두 숫자의 부등호 방향은 '작다' 또는 '크다' 어느 쪽이든 상관없습니다.

예를 들어 입력이 nums = [1, 2, 6, 4, 5]라면 출력은 4가 됩니다. 가장 긴 교차 부등식 부분 리스트가 [2, 6, 4, 5]이고, 이는 2 < 6 > 4 < 5를 만족하기 때문입니다.

해결 접근 방법

이 문제는 다음 단계에 따라 해결할 수 있습니다.

함수 get_direction(a, b)를 정의합니다.
- a와 b가 같으면 0, a < b이면 -1, 그 외(즉 a > b)에는 1을 반환합니다.
리스트의 길이가 2보다 작으면 해당 길이를 그대로 반환합니다.
max_length, cur_length를 1로, last_direction을 0으로 초기화합니다.
i를 0부터 (리스트 길이 - 2)까지 반복하면서 다음을 수행합니다.
- direction을 get_direction(nums[i], nums[i + 1])의 결과로 설정합니다.
- direction이 0이면(두 값이 같으면) cur_length를 1로 초기화합니다.
- direction이 last_direction과 같으면(부등호 방향이 연속으로 같으면) cur_length를 2로 초기화합니다.
- 그 외의 경우에는 cur_length를 1 증가시킵니다.
- max_length를 max_length와 cur_length 중 큰 값으로 갱신합니다.
- last_direction을 현재 direction으로 업데이트합니다.
반복이 끝나면 max_length를 반환합니다.

이 알고리즘은 리스트를 한 번만 순회하므로 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.

구현 예제

class Solution:
    def solve(self, nums):
        if len(nums) < 2:
            return len(nums)
        def get_direction(a, b):
            return 0 if a == b else -1 if a < b else 1
        max_length = 1
        cur_length = 1
        last_direction = 0
        for i in range(len(nums) - 1):
            direction = get_direction(nums[i], nums[i + 1])
            if direction == 0:
                cur_length = 1
            elif direction == last_direction:
                cur_length = 2
            else:
                cur_length += 1
            max_length = max(max_length, cur_length)
            last_direction = direction
        return max_length
ob = Solution()
nums = [1, 2, 6, 4, 5]
print(ob.solve(nums))

입력

[1, 2, 6, 4, 5]