128. longest-consecutive-sequence(LeetCode)

리스트 안에 순차적인 sequence가 있을 건데 그게 가장 긴 것을 출력하라는 문제이다. 

예를 들어 [1,2,3,4, 101, 102, 103, 104, 105] 이렇게 있다고 치면 여기서 가장 긴 sequence는 101, 102, 103, 104, 105가 되기 때문에 5를 출력 해내야 한다.

 

이걸 어떻게 풀 수 있을까?

일단은 먼저 리스트에 중복이 있으면 안되니까 중복을 제거해야한다. 어떻게? 파이썬에서는 아주 쉽게 Set함수를 이용해서 중복을 제거해버리면 된다.

 

두번째로는 반복문을 돌리면서 이 숫자가 sequence가 시작하는 숫자인지 아닌지를 판별하고 시작하는 숫자이면 그 숫자를 시작으로 다음 숫자가 있는지 Set 안에서 확인하면 된다. 

 

class Solution(object):
    def longestConsecutive(self, nums):
        num_set = set(nums) // set으로 변환
        longest = 0

        for num in num_set:
        	// 시작하는 숫자인지 체크
            if num - 1 not in num_set:
                current_num = num
                current = 1
				
                // 다음 숫자가 set에 있는지 확인
                while current_num + 1 in num_set:
                    current_num += 1
                    current += 1
                longest = max(longest, current)
        return longest