[Python] Longest Consecutive Sequence

문제 출처: 128. Longest Consecutive Sequence

코드 분석

1. 초기화:

• longest = 0: 최장 연속 부분 수열의 길이를 저장하는 변수
• num_dict = {}: 주어진 숫자들을 True로 저장하는 딕셔너리 (set과 유사한 역할)

1. 숫자 저장 (딕셔너리 활용)

• for num in nums: 루프를 돌면서 num_dict[num] = True로 설정하여 중복된 숫자를 제거하고 빠른 조회가 가능하게 만듦.
• 예제 입력 [6, 7, 100, 5, 4, 4]을 처리하면 {6: True, 7: True, 100: True, 5: True, 4: True}가 저장됨.

1. 연속된 수열 찾기

• for num in num_dict:를 반복하면서 num - 1이 딕셔너리에 없으면 해당 숫자가 새로운 연속 수열의 시작점임.
• cnt = 1로 초기화하고 target = num + 1부터 연속된 숫자가 있는지 확인.
• while target in num_dict:를 이용해 연속된 숫자를 찾고 cnt += 1로 증가.
• 최댓값을 longest = max(longest, cnt)로 갱신.

예제 실행 과정 ([6, 7, 100, 5, 4, 4])

• num_dict = {6: True, 7: True, 100: True, 5: True, 4: True}
• num = 6 → 5가 존재하므로 건너뜀
• num = 7 → 6이 존재하므로 건너뜀
• num = 100 → 99가 없으므로 시작 (cnt = 1, 종료)
• num = 5 → 4가 존재하므로 건너뜀
• num = 4 → 3이 없으므로 시작
• target = 5 → 존재 (cnt = 2)
• target = 6 → 존재 (cnt = 3)
• target = 7 → 존재 (cnt = 4)
• target = 8 → 없음 (종료)
• longest = max(1, 4) = 4

결과

• 최장 연속 부분 수열은 [4, 5, 6, 7]이며, 길이는 4.
• 따라서 longestConsecutive([6, 7, 100, 5, 4, 4])의 반환값은 4.