파이썬으로 가장 긴 연속된 숫자 시퀀스 길이 구하기

정렬되지 않은 숫자 배열이 하나 주어졌다고 가정해 봅시다. 이때 우리는 연속된 요소들로 이루어진 가장 긴 시퀀스의 길이를 찾아야 합니다.

예를 들어 입력이 nums = [70, 7, 50, 4, 6, 5]라면, 가장 긴 연속 시퀀스는 [4, 5, 6, 7]이고 그 길이는 4이므로 출력값은 4가 됩니다.

문제 해결 접근 방법

이 문제는 집합(Set) 자료구조를 활용하면 매우 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 숫자가 연속 시퀀스의 시작점인 경우에만 시퀀스의 길이를 계산하는 것입니다. 시작점 여부를 판단하는 기준은 간단합니다. 바로 현재 숫자에서 1을 뺀 값(num - 1)이 집합에 존재하지 않으면, 해당 숫자가 어떤 시퀀스의 시작이라는 것입니다.

알고리즘 단계

• nums를 집합으로 변환하여 중복을 제거하고 O(1) 시간 탐색을 가능하게 만듭니다.

• max_cnt = 0으로 초기화합니다.

• 집합의 각 숫자 num에 대해 반복합니다.

  • num - 1이 집합에 없다면, 즉 num이 시퀀스의 시작점이라면 다음을 수행합니다.

    • cnt = 0으로 카운터를 초기화합니다.

    • num이 집합에 존재하는 동안 num을 1씩 증가시키고 cnt도 함께 증가시켜 연속 시퀀스의 길이를 셉니다.

    • max_cnt와 cnt 중 더 큰 값으로 max_cnt를 갱신합니다.

• 모든 숫자를 확인한 후 최종적으로 max_cnt를 반환합니다.

파이썬 구현 예제

class Solution:
    def solve(self, nums):
        nums = set(nums)
        max_cnt = 0
        for num in nums:
            if num - 1 not in nums:
                cnt = 0
                while num in nums:
                    num += 1
                    cnt += 1
                max_cnt = max(max_cnt, cnt)
        return max_cnt
ob = Solution()
nums = [70, 7, 50, 4, 6, 5]
print(ob.solve(nums))

입력

[70, 7, 50, 4, 6, 5]

출력

4

시간 복잡도 분석

겉보기에는 반복문이 중첩되어 있어 O(n²)처럼 보일 수 있지만, 실제 시간 복잡도는 O(n)입니다. 그 이유는 내부 while 루프가 오직 시퀀스의 시작점에서만 실행되기 때문입니다. 결과적으로 각 숫자는 최대 두 번만 방문되며, 전체 연산 횟수는 입력 크기에 선형적으로 비례합니다.

공간 복잡도 또한 집합에 모든 요소를 저장하므로 O(n)입니다. 정렬 기반 접근(O(n log n))보다 빠르며, 대량의 데이터에서도 효율적으로 동작하는 것이 이 알고리즘의 가장 큰 장점입니다.