View in English →

Code › algorithm-study

LeetCode 128 - Longest Consecutive Sequence

set을 사용해 연속 수열의 시작점에서만 길이를 계산하는 풀이

algorithmleetcodearrayhash-setpythonlearning

정렬 없이 가장 긴 연속 수열의 길이를 구하는 Medium 문제다. 모든 숫자에서 수열을 세기 시작하면 같은 구간을 반복해서 보게 되므로, 이전 숫자가 없는 값만 시작점으로 삼는 방식으로 정리했다.

문제 링크 & 설명

  • 문제 링크: 128. Longest Consecutive Sequence
  • 요약: 정수 배열 nums가 주어졌을 때, 연속된 정수로 만들 수 있는 가장 긴 수열의 길이를 반환하는 문제.

예를 들어 입력이 이렇게 주어진다고 해보자.

nums = [100, 4, 200, 1, 3, 2]

이 배열에서 가장 긴 연속 수열은 [1, 2, 3, 4]이고, 길이는 4다. 배열 안에서 원소들이 정렬되어 있지는 않지만, 값 기준으로 연속된 숫자를 찾아야 한다.

접근 방법

정렬을 하면 인접한 값을 비교하면서 연속 구간을 셀 수 있다. 다만 정렬 비용이 O(n log n)이기 때문에, set으로 값의 존재 여부를 평균 상수시간에 확인해서 정렬 비용을 피한다.

먼저 nums를 set으로 바꾼다. 이렇게 하면 어떤 값이 배열에 있는지 바로 알아낼 수 있다.

num_set = set(nums)

그 다음 모든 숫자를 순회하되, 아무 숫자에서나 수열을 시작하지 않는다. 현재 값이 num일 때 num - 1이 set 안에 있다면, num은 어떤 연속 수열의 중간에 있는 값이다. 예를 들어 3을 보고 있는데 2가 이미 있다면, 3에서 새로 시작할 필요가 없고 1이나 2 쪽에서 시작했을 때 같은 수열을 한 번에 셀 수 있다.

if num - 1 in num_set:
    continue

num - 1이 없다면 그 숫자는 연속 수열의 시작점이다. 그때부터 cur_num을 하나씩 늘리면서 set 안에 값이 존재하는 동안 streak을 증가시킨다.

streak = 0
cur_num = num

while cur_num in num_set:
    streak += 1
    cur_num += 1

for loop 안에 while loop가 있어서 nested loop 구조이지만, 실제로는 시작점에서만 while loop를 돈다. 중간 값들은 num - 1 조건에서 건너뛰기 때문에 같은 연속 구간을 여러 번 다시 세지 않는다.

트러블 슈팅

처음에는 바깥쪽 for loop에서 num_set이 아니라 nums를 그대로 순회했다. 값의 존재 여부는 set으로 확인하니까 괜찮다고 생각했지만, nums에는 중복 값이 남아 있어서 같은 시작점을 여러 번 다시 처리할 수 있었다.

예를 들어 시작점에 해당하는 값이 입력 배열에 여러 번 들어 있으면, 그 값이 나올 때마다 while loop가 같은 연속 구간을 다시 센다. 그래서 중복을 제거한 num_set을 순회하도록 바꾸었고, 각 시작점이 한 번만 처리되면서 시간초과를 피할 수 있었다.

복잡도 분석

  • 시간 복잡도: O(n)

    • nums를 set으로 만드는 데 O(n)이 들고, num_set을 순회하는 for loop와 시작점에서만 도는 while loop를 합쳐도 최대 O(2n) 수준이다. 상수는 제거하므로 최종 시간복잡도는 O(n)이다.

  • 공간 복잡도: O(n)

    • num_set이 입력 크기에 비례하는 공간을 사용한다.

이 풀이에서 중요한 부분은 set 자체보다 시작점을 고르는 조건이다. num - 1이 없는 값에서만 길이를 세면 정렬 없이도 전체 반복 횟수를 선형으로 묶을 수 있다.

최적화 코드

from typing import List, Set

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        num_set: Set[int] = set(nums)
        max_streak = 0

        for num in num_set:
            if num - 1 in num_set:
                continue

            streak = 0
            cur_num = num

            while cur_num in num_set:
                streak += 1
                cur_num += 1

            max_streak = max(streak, max_streak)

        return max_streak

요약 및 회고

이 문제는 set으로 존재 여부를 빠르게 확인하는 것에서 시작하지만, 모든 숫자를 출발점으로 삼지 않는 조건이 더 중요했다. 현재 숫자보다 하나 작은 값이 있으면 그 숫자는 이미 어떤 수열의 중간에 있으므로 건너뛰고, 시작점에서만 길이를 세면 정렬 없이 시간복잡도 O(n)으로 처리할 수 있다.