Python으로 중복 없는 가장 긴 연속 부분 리스트의 길이 구하기

숫자로 이루어진 리스트 nums가 주어졌을 때, 모든 요소가 서로 중복되지 않는(고유한) 가장 긴 연속 부분 리스트의 길이를 구하는 문제입니다.

예를 들어 입력이 nums = [6, 2, 4, 6, 3, 4, 5, 2]라면 출력은 5가 됩니다. 고유한 요소로만 구성된 가장 긴 연속 구간이 [6, 3, 4, 5, 2]이고, 그 길이가 5이기 때문입니다.

문제 해결 접근 방법

이 문제는 슬라이딩 윈도우(Sliding Window) 기법과 해시 맵(딕셔너리)을 활용하면 효율적으로 해결할 수 있습니다. 각 요소가 마지막으로 등장한 인덱스를 딕셔너리에 기록하고, 중복된 요소를 만나면 윈도우의 시작점(head)을 해당 위치 다음으로 이동시키는 방식입니다.

구체적인 알고리즘 단계는 다음과 같습니다.

• head := 0, dct := 빈 딕셔너리로 초기화합니다.
• max_dist := 0으로 최대 길이를 초기화합니다.
• 리스트의 각 인덱스 i와 요소 num에 대해 반복합니다.
  • num이 dct에 존재하고 dct[num] >= head라면, head := dct[num] + 1로 윈도우 시작점을 갱신합니다.
  • dct[num] := i로 현재 인덱스를 저장합니다.
  • i - head + 1 > max_dist라면 max_dist를 갱신합니다.
• 최종적으로 max_dist를 반환합니다.

예제 코드

다음 구현을 통해 더 잘 이해할 수 있습니다.

class Solution:
    def solve(self, nums):
        head = 0
        dct = {}
        max_dist = 0
        for i, num in enumerate(nums):
            if num in dct and dct[num] >= head:
                head = dct[num] + 1
            dct[num] = i
            if i - head + 1 > max_dist:
                max_dist = i - head + 1
    return max_dist

ob = Solution()
nums = [6, 2, 4, 6, 3, 4, 5, 2]
print(ob.solve(nums))

입력

[6, 2, 4, 6, 3, 4, 5, 2]

출력

5

시간 복잡도 분석

이 알고리즘은 리스트를 한 번만 순회하므로 시간 복잡도는 O(n)이며, 각 요소의 마지막 등장 위치를 저장하는 딕셔너리 때문에 공간 복잡도 역시 O(n)입니다. 브루트 포스 방식으로 모든 부분 리스트를 검사하는 O(n²) 방식보다 훨씬 효율적입니다.