Algorithms

[LeetCode] 128. Longest Consecutive Sequence 풀이 (Java)

작은별._. 2026. 2. 8. 19:47
728x90
반응형

✔️ 오늘의 리트코드 공부 기록 – Longest Consecutive Sequence

 

문제 요약 (Longest Palindromic Substring)

정수 배열이 주어질 때, 연속된 숫자로 이루어진 수열의 가장 긴 길이를 구하라.
단, 시간복잡도는 O(n).

 

문제링크: https://leetcode.com/problems/longest-consecutive-sequence

 

🤔 처음 떠올린 아이디어

처음에는 이렇게 생각했다.

어차피 연속된 숫자들은 하나의 덩어리 아닌가?
  1. 숫자를 HashSet에 모두 넣고
  2. 아무 숫자 하나를 꺼낸 뒤
  3. 그 숫자를 기준으로 왼쪽(cur-1), 오른쪽(cur+1)으로 계속 확장.
  4. 확장한 숫자들을 Set에서 제거
  5. 길이를 계산하고 최대 길이 갱신.
  6. 다음 덩어리로 이동.

그러면 하나의 “연속 덩어리”를 한 번에 처리할 수 있을 것 같았다.

 

이 방식은 직관적으로 이렇게 보였다.

한 번 방문한 숫자는 다시 보지 않겠다.

 

코드 (Java)

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int longestConsecutive(int[] nums) {

        if (nums == null || nums.length == 0) return 0;

        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }

        int longest = 0;

        while (!numSet.isEmpty()) {

            // 아무 원소 하나 꺼내기
            int cur = numSet.iterator().next();
            numSet.remove(cur);

            int length = 1;

            // 왼쪽 확장
            int prev = cur - 1;
            while (numSet.contains(prev)) {
                numSet.remove(prev);
                prev--;
                length++;
            }

            // 오른쪽 확장
            int next = cur + 1;
            while (numSet.contains(next)) {
                numSet.remove(next);
                next++;
                length++;
            }

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

        return longest;
    }
}

 

💭 장점

  • ✔ 직관적이다
  • ✔ “덩어리 단위로 처리”하는 느낌이 명확하다
  • ✔ 각 숫자를 한 번만 제거하므로 이론상 O(n)

⚠️ 단점

이 방식은 생각보다 느릴 수 있다.

 

이유:

  • while 루프 안에서 매번 iterator 생성
  • remove 연산 반복
  • HashSet 내부 재해싱 가능성

즉, 이론은 O(n)이지만 상수 비용이 크다.

그래서 일부 환경에서는 TLE가 날 수 있다. (리트코드 제출시 실제로 시간초과가 났다.)

 

💡 이건 덩어리 제거 문제가 아니다.

처음에는 이렇게 생각했다.

“연속된 숫자는 하나의 덩어리니까
한 번에 확장해서 제거하면 되지 않을까?”

 

그래서 remove 방식으로 접근했다.

 하지만 풀다 보니 이런 의문이 생겼다.

“굳이 지울 필요가 있을까?”

 

remove 하면서 처리하는 대신,

“시작점에서만 확장하면 되지 않을까?”

 

🎯 결정적인 조건: 시작점만 확장하라

연속 수열은 항상 가장 작은 값에서 시작한다.
즉, num - 1이 존재하지 않을 때만 그 숫자를 시작점으로 본다.

 

  • num-1이 존재하지 않을 때만 확장 시작
  • num-1이 존재하면 이미 다른 수에서 처리된 덩어리
  • 이렇게 하면 각 숫자는 최대 한 번만 사용 → O(n)

예시: [1,2,3,4]

  • 1 → 시작점, 확장
  • 2,3,4 → 시작점 아님, 이미 처리됨

🧩 최종 알고리즘 흐름

1️⃣ 모든 숫자를 HashSet에 넣는다
2️⃣ 각 숫자에 대해 반복한다
3️⃣ 만약 num-1이 없다면 → 시작점
4️⃣ num+1이 있는 동안 계속 확장
5️⃣ 최대 길이 갱신

 

remove는 필요 없다. 중복 확장도 발생하지 않는다.

코드 (Java)

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int longestConsecutive(int[] nums) {

        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }

        int longest = 0;

        for (int num : set) {

            // 시작점일 때만 확장
            if (!set.contains(num - 1)) {

                int current = num;
                int length = 1;

                while (set.contains(current + 1)) {
                    current++;
                    length++;
                }

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

        return longest;
    }
}

 

📈 시간/공간 복잡도 분석

시간복잡도 O(n)

  • 각 숫자는:
    1️⃣ 시작점 검사 1번
    2️⃣ 확장에서 최대 1번 사용
  • 모든 숫자는 최대 한 번만 while 안에 들어감
  • 따라서 전체 반복 횟수는 숫자 개수 n에 비례 → O(n)

공간복잡도 O(n)

  • HashSet을 사용하여 모든 숫자를 저장
  • 추가 자료구조는 없고, 확장/계산에 상수 공간만 사용
  • 따라서 공간복잡도는 입력 배열 크기 n에 비례 → O(n)

 

📝 이번 문제에서 얻은 깨달음

  • 모든 지점에서 시작하지 말고, 시작 조건을 만족하는 지점만 시작하라
  • 직관적 방법과 효율적 방법의 차이를 이해하면 O(n) 알고리즘 설계가 보인다
    • 왜 ‘시작점 조건’ 하나만 체크해도 충분한지를 이해하면 단순 직관적 아이디어를 실제 최적화 알고리즘으로 바꾸는 과정이 보인다
  • HashSet + 시작점 조건 → 중복 검사 없이 빠른 연속 수열 계산 가능
728x90
반응형