[DSA][Array & Hashing] 08. Longest Consecutive Sequence

LeetCode 128

 

08. Longest Consecutive Sequence

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
You must write an algorithm that runs in O(n) time.

 

 

[질문하기]

- 음수가 포함될 수 있나요? YES

- 정수 배열에 중복된 값이 존재할 수 있나요? YES

 

 

[아이디어]

연속된 숫자를 판단할 때, num을 기준으로 num + 1이 있는지 확인하자. 그러기 위해 탐색에 유리한 자료구조인 set을 사용하자.

 

 

[풀이 1] Set

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        numSet = set(nums)
        maxCnt = 0

        for num in numSet:
            if num - 1 not in numSet:
                count = 1
                while num + count in numSet:
                    count += 1
                maxCnt = max(maxCnt, count)

        return maxCnt

연속된 숫자를 어떻게 판단할까?

어떤 수 x가 있을 때 x + 1도 있으면 연속된 숫자가 있다고 생각할 수 있다.

왜냐면 특정 원소의 존재 유무는 set 자료구조로 O(1)에 확인할 수 있기 때문이다.

여기서 추가로, 이미 하나의 연속된 구간에 포함된 x, y가 있다고 할 때, x < y인 x에 대해 연속된 구간의 길이를 구했다면, y부터는 다시 구할 필요가 없기 때문에 이 부분을 구현하면 최적화가 가능하다.

그럼 그 전의 원소가 있었는지 어떻게 확인할까? y에 대해 y - 1만 set에 있다면 그 이전의 원소에 대해서는 이미 (혹은 나중에라도) 확인을 할 것임을 알 수 있다.   

 

⏱️ 시간복잡도

정수 배열을 한번 순회하기 때문에 O(n)

🧠 공간복잡도

배열만큼의 공간이 필요하므로 O(n)