숫자로 이루어진 리스트 nums가 주어졌을 때, 리스트에서 최대 한 개의 원소를 제거할 수 있다고 가정하고, 연속적이면서 엄격하게(엄밀히) 증가하는 부분 리스트의 최대 길이를 구하는 문제입니다.
예를 들어 입력이 nums = [35, 5, 6, 7, 8, 9, 12, 11, 26]라면 출력은 7이 됩니다. 12를 제거하면 리스트는 [5, 6, 7, 8, 9, 11, 26]이 되어 길이 7짜리 연속적인 엄격 증가 부분 리스트가 만들어지며, 이것이 가능한 가장 긴 경우이기 때문입니다.
문제 해결 접근 방식
이 문제는 동적 계획법(DP)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 인덱스를 기준으로 두 방향의 증가 구간 길이를 미리 계산해 두는 것입니다.
- end[i] : 인덱스 i에서 끝나는 가장 긴 엄격 증가 부분 리스트의 길이
- start[i] : 인덱스 i에서 시작하는 가장 긴 엄격 증가 부분 리스트의 길이
두 배열을 모두 완성한 뒤, 각 위치 k에 대해 nums[k-1] < nums[k+1] 조건을 만족한다면 k번째 원소를 제거했을 때 좌우 구간을 서로 연결할 수 있습니다. 따라서 end[k-1] + start[k+1] 값을 후보로 삼아 최댓값을 갱신해 나갑니다.
알고리즘 단계
- nums가 비어 있으면 0을 반환합니다.
- nums와 같은 크기의 배열 end와 start를 만들고, 모든 값을 1로 초기화합니다.
- i를 1부터 len(nums)-1까지 순회하며, nums[i] > nums[i-1]이면 end[i] = end[i-1] + 1로 갱신합니다.
- j를 len(nums)-2부터 0까지 역순으로 순회하며, nums[j+1] > nums[j]이면 start[j] = start[j+1] + 1로 갱신합니다.
- res를 end 배열과 start 배열 요소들의 최댓값으로 설정합니다.
- k를 1부터 len(nums)-2까지 순회하며, nums[k-1] < nums[k+1]이면 res = max(res, end[k-1] + start[k+1])로 갱신합니다.
- res를 반환합니다.
구현 예시
다음 코드를 통해 더 자세히 이해해 보겠습니다.
def solve(nums): if not nums: return 0 end = [1 for i in nums] start = [1 for i in nums] for i in range(1, len(nums)): if nums[i] > nums[i - 1]: end[i] = end[i - 1] + 1 for j in range(len(nums) - 2, -1, -1): if nums[j + 1] > nums[j]: start[j] = start[j + 1] + 1 res = max(max(end), max(start)) for k in range(1, len(nums) - 1): if nums[k - 1] < nums[k + 1]: res = max(res, end[k - 1] + start[k + 1]) return res nums = [35, 5, 6, 7, 8, 9, 12, 11, 26] print(solve(nums))
입력
[35, 5, 6, 7, 8, 9, 12, 11, 26]
출력
7
복잡도 분석
리스트를 세 번 순회하므로 시간 복잡도는 O(n)이며, 두 개의 보조 배열을 사용하므로 공간 복잡도 역시 O(n)입니다. 브루트포스 방식처럼 매 원소를 제거해 보며 전체를 검사하는 O(n²) 방식보다 훨씬 효율적입니다.