문제 개요
모든 요소가 고유(unique)한 숫자 리스트 nums가 주어졌을 때, 서로 연속된 값들로만 이루어진 가장 긴 부분 리스트(연속 하위 목록)의 길이를 찾는 것이 목표입니다.
예를 들어, 입력이 nums = [3, 6, 7, 5, 4, 9]라고 한다면 출력은 5가 됩니다. 부분 리스트 [3, 6, 7, 5, 4]가 3부터 7까지의 모든 연속적인 값을 포함하고 있기 때문입니다.
접근 방법
이 문제의 핵심 아이디어는 다음과 같습니다. 어떤 구간 [i, j] 안에서 최댓값과 최솟값의 차이가 구간의 길이와 정확히 일치한다면, 그 구간의 요소들은 반드시 연속된 값이라는 뜻입니다. 모든 요소가 고유하다는 조건 덕분에 중복 없이 이 판별이 가능합니다.
구체적인 해결 단계는 다음과 같습니다.
ret := 0으로 결과 변수 초기화- i를 0부터 nums의 크기 - 1까지 반복:
lhs := nums[i](구간 최솟값)rhs := nums[i](구간 최댓값)- j를 i부터 nums의 크기 - 1까지 반복:
lhs := lhs와 nums[j] 중 최솟값rhs := rhs와 nums[j] 중 최댓값- (rhs - lhs)가 (j - i)와 같다면:
ret := ret와 (j - i + 1) 중 최댓값
- 최종적으로
ret반환
이 알고리즘은 두 개의 중첩 반복문을 사용하므로 시간 복잡도는 O(n²)이며, 추가 공간은 상수 수준인 O(1)입니다.
예제 코드
아래 구현을 통해 더 잘 이해해 보겠습니다.
def solve(nums): ret = 0 for i in range(len(nums)): lhs = nums[i] rhs = nums[i] for j in range(i, len(nums)): lhs = min(lhs, nums[j]) rhs = max(rhs, nums[j]) if rhs - lhs == j - i: ret = max(ret, j - i + 1) return ret nums = [3, 6, 7, 5, 4, 9] print(solve(nums))
실행 결과
입력:
[3, 6, 7, 5, 4, 9]
출력:
5
결과가 5인 이유는 인덱스 0부터 4에 해당하는 부분 리스트 [3, 6, 7, 5, 4]가 3~7 사이의 모든 연속된 값을 담고 있고, 이보다 긴 연속 구간은 존재하지 않기 때문입니다.