128. Longest Consecutive Sequence

난이도: 중간 (Medium)

링크: LeetCode 128

풀이 날짜: 2025/10/22

 

1. 문제 이해

정수 배열 nums가 주어질 때, 연속된 정수로 이루어진 가장 긴 시퀀스 길이를 구하는 문제이다. 그리고 연속된 수들은 배열 내에서 순서대로 나열되어 있을 필요는 없다. 핵심은 연속된 수들을 효율적으로 찾는 방법이다.

 

2. 접근 방식 — HashSet 활용

단순히 배열을 정렬한 후 연속 시퀀스를 찾으면 O(n log n) 시간(sort 정렬)이 걸리는데,  하지만 HashSet을 사용하면 O(n) 시간에 해결 가능하다.

 

핵심 아이디어

1. 모든 수를 HashSet에 저장한다.
2. 각 수가 연속 시퀀스의 시작점인지 확인한다. 즉, 시작점 조건은 num - 1이 Set에 없는 경우.
3. 시작점이면, while 문을 이용하여, num부터 연속된 수를 하나씩 세어 길이를 구한다.
4. 모든 시작점에 대해 반복하며 최대 길이를 갱신한다.

핵심 포인트는 시작점만 검사하면 중복 계산을 피할 수 있다는 것인데, 왜냐하면 시작점이 아닌 값은 시작점인 값에서 연속된 수를 셀 때 포함되기 때문이다. 

 

3. 풀이 코드 (HashSet)

var longestConsecutive = function(nums) {
  const numsSet = new Set(nums); 
  let longest = 0;

  for (const num of numsSet) {
    const isStarting = !numsSet.has(num - 1); // 시작점 체크
    if (isStarting) {
      let length = 1;
      let current = num;
      
      // while 문에서 업데이트 하기 위해 num 이 아닌 current 를 사용해야 한다.
      while (numsSet.has(current + 1)) {
        length++;
        current++;
      }

      longest = Math.max(longest, length);
    }
  }

  return longest;
};

 

 

예시 시나리오1

Input: [100, 4, 200, 1, 3, 2], 최종 결과 -> 4

단계수	HashSet	포함 여부	현재 길이	최대 길이
1	100	시작점	1	1
2	4	시작점 아님(4단계에 포함됨)	-	1
3	200	시작점	1	1
4	1	시작점	1 → 2 → 3 → 4	4 ✅

 

예시 시나리오2

Input: [8,3,7,2,5,0,4,6,0,1], 최종 결과 → 9

단계	탐색 중인 숫자(num)	시작점 여부 (num-1 존재?)	연속 길이	탐색최장 길이(longest)
1	8	시작점 아님 (7 존재)	-	0
2	3	시작점 아님 (2 존재)	-	0
3	7	시작점 아님 (6 존재)	-	0
4	2	시작점 아님 (1 존재)	-	0
5	5	시작점 아님 (4 존재)	-	0
6	0	시작점 (−1 없음)	0→1→2→3→4→5→6→7→8 (9단계)	9
7	4	시작점 아님 (3 존재)	-	9
8	6	시작점 아님 (5 존재)	-	9
9	1	시작점 아님 (0 존재)	-	9 ✅

시간 및 공간 복잡도

항목	복잡도	설명
시간	O(n)	HashSet에 삽입 및 각 수에 대해 연속 시퀀스 검사
공간	O(n)	HashSet 저장

 

4. 풀이 코드 (정렬 기반 — 비효율적)

var longestConsecutive = function(nums) {
  if (nums.length === 0) return 0;
  const sortedNums = Array.from(new Set(nums)).sort((a, b) => a - b);
  
  let result = 1;
  let tempo = 1;

  for (let i = 1; i < sortedNums.length; i++) {
    if (sortedNums[i] - sortedNums[i - 1] === 1) {      
      tempo++;      
    } else {      
      tempo = 1;
    }
    result = Math.max(result, tempo);
  }

  return result;
};

이 방법은 정렬 때문에 O(n log n) 시간 복잡도를 갖는다. 연속 수를 찾는 아이디어는 동일하지만, 최적화된 HashSet 방식이 더 효율적입니다.

 

5. 핵심 정리

• 문제 유형: HashSet, Array, 연속 수 시퀀스
• 핵심 아이디어:
  1. 각 수가 연속 시퀀스 시작점인지 확인
  2. 시작점이면 연속 수 길이를 계산
  3. 최대 길이를 갱신
• 시간 복잡도: O(n)
• 공간 복잡도: O(n)
• 포인트: 시작점만 검사 → 중복 계산 방지