숫자로 이루어진 리스트 nums가 주어졌을 때, 리스트에서 원소를 최대 하나 제거할 수 있다고 가정해 봅시다. 이때 만들 수 있는 가장 긴 연속된(strictly increasing) 엄격히 증가하는 부분 리스트의 최대 길이를 구하는 것이 이번 문제입니다.
예를 들어 입력이 nums = [30, 11, 12, 13, 14, 15, 18, 17, 32]라면 출력은 7이 됩니다. 값 18을 제거하면 [11, 12, 13, 14, 15, 17, 32]라는 가장 긴 연속 증가 부분 리스트를 얻을 수 있고, 그 길이가 7이기 때문입니다.
풀이 접근 방식
이 문제는 동적 계획법(DP)을 활용한 전처리 방식으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- pre[i] : 인덱스 i에서 끝나는 왼쪽 방향 최장 증가 연속 구간의 길이
- suff[i] : 인덱스 i에서 시작하는 오른쪽 방향 최장 증가 연속 구간의 길이
두 배열을 미리 계산해 두면, 특정 원소 하나를 제거했을 때 양옆 구간을 이어 붙인 길이를 O(1) 만에 확인할 수 있습니다.
알고리즘 단계
- n := nums의 크기
- pre := 크기가 n이고 모든 값을 1로 초기화한 리스트
- i를 1부터 n-1까지 순회하며, nums[i] > nums[i-1]이면 pre[i] := pre[i-1] + 1
- suff := 크기가 n이고 모든 값을 1로 초기화한 리스트
- i를 n-2부터 0까지 역순으로 순회하며, nums[i] < nums[i+1]이면 suff[i] := suff[i+1] + 1
- ans := max(pre)와 max(suff) 중 더 큰 값 (원소를 제거하지 않는 경우)
- i를 1부터 n-2까지 순회하며, nums[i-1] < nums[i+1]이면(i번째 원소를 제거해 양옆을 연결할 수 있으면) ans := max(ans, pre[i-1] + suff[i+1])
- ans 반환
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
구현 예제
class Solution:
def solve(self, nums):
n = len(nums)
# pre[i]: 인덱스 i에서 끝나는 최장 증가 구간의 길이
pre = [1] * n
for i in range(1, n):
if nums[i] > nums[i - 1]:
pre[i] = pre[i - 1] + 1
# suff[i]: 인덱스 i에서 시작하는 최장 증가 구간의 길이
suff = [1] * n
for i in range(n - 2, -1, -1):
if nums[i] < nums[i + 1]:
suff[i] = suff[i + 1] + 1
# 원소를 제거하지 않는 경우
ans = max(max(pre), max(suff))
# 원소 하나를 제거하여 양옆 구간을 연결하는 경우
for i in range(1, n - 1):
if nums[i - 1] < nums[i + 1]:
ans = max(ans, pre[i - 1] + suff[i + 1])
return ans
ob = Solution()
nums = [30, 11, 12, 13, 14, 15, 18, 17, 32]
print(ob.solve(nums))
입력
[30, 11, 12, 13, 14, 15, 18, 17, 32]
출력
7
복잡도 분석
이 알고리즘은 리스트를 세 번 선형 순회하므로 시간 복잡도는 O(n)이며, 두 개의 보조 배열을 사용하므로 공간 복잡도 역시 O(n)입니다. 리스트의 길이가 1 이하인 경우에는 항상 그 길이 자체가 정답이 되므로 별도의 예외 처리 없이도 올바르게 동작합니다.