문제 개요
숫자로 이루어진 리스트 nums가 주어졌을 때, 가장 긴 증가 부분 수열(Longest Increasing Subsequence)의 길이를 구하는 문제입니다. 특별한 조건은 부분 수열이 리스트의 끝에 도달하면 다시 처음으로 돌아가 이어질 수 있다는 점, 즉 리스트를 원형(circular) 구조로 취급한다는 것입니다.
예를 들어 입력이 nums = [6, 5, 8, 2, 3, 4]라면 정답은 5입니다. 리스트의 끝에서 처음으로 감싸 연결했을 때 가장 긴 증가 부분 수열이 [2, 3, 4, 6, 8]이 되기 때문입니다.
해결 전략
핵심 아이디어는 간단합니다. 리스트를 두 번 이어 붙여 원형 구조를 선형으로 펼친 뒤, 각 시작 위치마다 LIS 알고리즘을 적용하는 것입니다. 원형 수열의 길이는 원래 리스트 길이를 넘을 수 없으므로, 각 시작점에서 길이 n짜리 구간만 검사하면 모든 경우를 커버할 수 있습니다.
- a: nums를 두 번 이어 붙여 만든 크기 2배짜리 리스트를 생성합니다.
- ans: 최종 답을 저장할 변수로 0으로 초기화합니다.
- i를 0부터 nums의 길이까지 반복하며 다음을 수행합니다.
- dp: 현재 구간의 증가 수열 정보를 저장할 새 리스트를 만듭니다.
- j를 i부터 len(nums) + i - 1까지 반복하며 다음을 수행합니다.
- n := a[j]
- k := 이진 탐색(bisect_left)으로 n이 삽입될 가장 왼쪽 인덱스를 찾습니다.
- k가 dp의 길이와 같으면 n을 dp의 끝에 추가하고, 그렇지 않으면 dp[k] = n으로 기존 값을 교체합니다.
- ans := ans와 len(dp) 중 더 큰 값으로 갱신합니다.
- 모든 반복이 끝나면 ans를 반환합니다.
파이썬 구현 코드
import bisect
class Solution:
def solve(self, nums):
a = nums + nums
ans = 0
for i in range(len(nums)):
dp = []
for j in range(i, len(nums) + i):
n = a[j]
k = bisect.bisect_left(dp, n)
if k == len(dp):
dp.append(n)
else:
dp[k] = n
ans = max(ans, len(dp))
return ans
ob = Solution()
nums = [4, 5, 8, 2, 3, 4]
print(ob.solve(nums))
입력
[4, 5, 8, 2, 3, 4]
출력
5
동작 원리 살펴보기
코드에서 사용된 bisect.bisect_left(dp, n)은 항상 정렬된 상태를 유지하는 dp 리스트 안에서 n이 들어갈 위치를 O(log n) 시간에 찾아주는 이진 탐색 함수입니다. 새 값이 dp의 모든 원소보다 크면 리스트 끝에 추가되고, 그렇지 않으면 해당 위치의 기존 값을 더 작은 값으로 교체합니다. 이렇게 하면 dp의 길이가 곧 현재 구간에서의 가장 긴(엄격하게 증가하는) 부분 수열의 길이가 됩니다.
예제 입력 [4, 5, 8, 2, 3, 4]의 경우, 시작점을 값 2로 잡으면 두 배로 늘린 리스트에서 [2, 3, 4, 4, 5, 8] 구간을 검사하게 되고, 여기서 얻을 수 있는 가장 긴 증가 부분 수열은 [2, 3, 4, 5, 8]로 길이가 5입니다. 따라서 최종 출력은 5가 됩니다.
시간 복잡도
시작점이 n개이고 각 시작점마다 길이 n의 구간에 대해 O(log n) 이진 탐색을 수행하므로, 전체 시간 복잡도는 O(n² log n)입니다. 추가로 사용하는 공간은 dp 리스트 등 O(n) 수준입니다.