Today's Challenge

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

Longest Consecutive Sequence - LeetCode

문제가 단순 LIS를 구하는 건 줄 알았는데, 그냥 연속되는 숫자의 최장 길이를 구하는 거였다.
정렬하고 set 하면 금방 끝날 듯한 문제인데, set만을 이용해서 푸는 솔루션을 찾아서 적용해봄.

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        lis = 0
        num_set = set(nums)
        
        for num in num_set:
            if num - 1 not in num_set:
                cur_num = num
                cur_streak = 1
                
                while cur_num + 1 in num_set:
                    cur_num += 1
                    cur_streak += 1
                
                lis = max(lis, cur_streak)
        
        return lis