Longest Consecutive Sequence(lcs.py)

---

[문제]

Given an unsorted array of integers nums, return the ength of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

[제한 사항]

• $0$ <= nums.length <= $105$
• $-10^9$ <= nums[i] <= $10^9$

[입출력 예]

Example 1

Input: nums = [100,4,200,1,3,2]
Output: 4

Example 2

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

[입출력 예에 대한 설명]

Example 1

Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

풀이

---

1차 시도

접근 방식

1. 시퀀스의 첫 숫자부터 끝까지 세는것이 중요해 보였다.
2. 어떤 시퀀스의 중간에서 끝까지 전부 세게 되면 시간 복잡도가 O(N^2)가 된다.
3. 따라서 리스트를 돌면서 숫자가 시퀀스의 중간 숫자인지, 새로운 숫자인지를 확인해야 할 것 같았다.
4. 중간 숫자인지 판단하는 기준으로 나보다 1 작은 숫자가 리스트에 있는지 확인하는 방법을 택했다.
5. 그러다보니 리스트보다 해시테이블로 저장해서 lookup이 빠르다는 것에 착안해 전체 리스트를 해시테이블로 가공했다.
6. 해시 테이블을 순회하면서 지금 보는 숫자가 시퀀스의 첫 숫자면 1을 더한 값이 있는지 확인하고, 있으면 계속해서 찾아가며 시퀀스 길이를 잰다.
7. 끝난 뒤 얻은 길이를 기존 맥스 길이와 비교하여 맥스 길이를 갱신해준다.

코드

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
       _dict = dict.fromkeys(nums, 0)
       ret = 0
       for num in _dict:
           # 현재 보고 있는 숫자가 시퀀스의 중간이 아닐때만 실행
           if num - 1 not in _dict:
               length = 1
               next = num + 1
               # 다음 숫자가 있을때 계속해서 찾으며 시퀀스 길이를 늘려나간다.
               while next in _dict:
                   next += 1
                   length += 1
                # 시퀀스를 다 찾으면 기존에 있던 가장 긴 길이와 현재 찾은 길이를 비교하여 갱신
               ret = max(ret, length)
       return ret

결과

배운점

• 어떤 상황에서는 다룰 데이터들을 밸류가 중요하지 않은 키값으로만 이루어진 해시테이블로 만들어서 다루는 것이 유리하다는 것을 배웠다.