← 전체 회차
A-009● Day 092026.05.11mediumleetcode #128neetcode150

최장 연속 수열

#array#hash-table#union-find
↗ leetcode #128 · longest-consecutive-sequence
01

문제

· problem
P.009

최장 연속 수열

↗ leetcode #128

정렬되지 않은 정수 배열 nums가 주어질 때, 연속된 정수들로 이루어진 최장 수열의 길이를 반환하세요. O(n) 시간에 실행되는 알고리즘을 작성해야 합니다.

제약
  • · 0 ≤ nums.length ≤ 10⁵
  • · -10⁹ ≤ nums[i] ≤ 10⁹
  • · 배열에는 중복된 원소가 포함될 수 있음 / Array may contain duplicate elements
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
[100,4,200,1,3,2]
4
example 2input → output
[0,3,7,2,5,8,4,6,0,1]
9
example 3input → output
[1,0,1,2]
3
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    연속 수열에서 각 원소는 정확히 몇씩 차이가 나야 하나요?
  • ☐
    수열이 배열 내에서 연속된 위치에 있어야 하나요?
  • ☐
    배열에 중복된 숫자가 있으면 어떻게 처리해야 하나요?
  • ☐
    배열을 정렬하면 쉽게 풀 수 있는데, 왜 O(n) 제약이 있나요?
  • ☐
    해시 집합(set)을 사용하지 않고도 O(n) 시간에 풀 수 있나요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 배열을 집합으로 변환
○
numSet = set(nums)
○
numSet = sorted(nums)
○
numSet = {n: True for n in nums}
step 2· 최장 수열 길이 초기화
○
longest = 0
○
longest = 1
○
longest = float('-inf')
step 3· 집합의 각 숫자 반복
○
for n in numSet:
○
for n in nums:
○
for i in range(len(numSet)):
step 4· 수열 시작점 확인│ 중첩
○
if (n - 1) not in numSet:
○
if (n + 1) not in numSet:
○
if n not in visited:
step 5· 수열 길이 초기화 및 확장│ │ 중첩
○
length = 1
○
length = 0
○
length = len([x for x in numSet if x >= n])
step 6· 연속된 숫자 세기│ │ 중첩
○
while (n + length) in numSet:
○
while (n + length) in numSet and length < 100:
○
while (n - length) in numSet:
step 7· 최대값 업데이트│ │ 중첩
○
longest = max(length, longest)
○
longest = length
○
longest += length
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class Solution:
2
    def longestConsecutive(self, nums: List[int]) -> int:
3
        numSet = set(nums)
4
        longest = 0
5
6
        for n in numSet:
7
            # check if its the start of a sequence
8
            if (n - 1) not in numSet:
9
                length = 1
10
                while (n + length) in numSet:
11
                    length += 1
12
                longest = max(length, longest)
13
        return longest
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
[100,4,200,1,3,2]
→
4
case 2
[0,3,7,2,5,8,4,6,0,1]
→
9
case 3
[1,0,1,2]
→
3
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.