[HashMap 문제] Leetcode 128. Longest Consecutive Sequence

문제

https://leetcode.com/problems/longest-consecutive-sequence/

상기 문제를 정렬되지 않은 배열 내에서 O(n) 속도로 즉 정렬을 사용하지 않고 가장 긴 연속된 수의 길이를 구하는 문제이다

문제풀이

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if len(nums) <= 0:
            return 0

        num_set = set(nums)  # 숫자를 집합으로 변환
        max_length = 0

        for num in num_set:
            if num - 1 not in num_set:
                current_num = num
                current_length = 1

                while current_num + 1 in num_set:
                    current_num += 1
                    current_length += 1

                max_length = max(max_length, current_length)

        return max_length

핵심 코드 설명

위 솔루션 기준에서 핵심은 하기 부분이라고 생각한다.

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

나는 이 문제에 접근할 때 우선 nums 내 원소를 dictionary Key로 만든 후 최소 값 원소부터 +1씩 더해가면서 최대길이를 산출하는 방식으로 처리하였는데 여기서 문제는 가령 [-99999999, 99999999 ]처럼 중간 값이 빈 경우 1씩 증감해나가면서 찾다보니 속도 이슈가 컸다. 이러한 문제를 예상하였지만 정렬되어 있지 않은 상태이다보니 중간에 비었는지 연속된 값이 존재할지 판단을 어떻게 할지가 가장 큰 고민이었다.
위 2줄 코드는 이를 완벽히 해결하는데 주어진 nums를 순회하는 시점에 num-1이 없다는 것이 확인되면 이는 최초 시작점으로 판단할 수 있게 된다.

Lookback

1. 이번 문제를 통해 hashmap 생성 후 num-1 값이 있는 것으로 시작점을 판단하는 아이디어는 꼭 익혀서 다음에 적용할 수 있도록 연습이 필요할 듯하다.