LeetCode-128 Longest Consecutive Sequence 파이썬 풀이

Longest Consecutive Sequence - LeetCode

문제

주어진 int형 배열안에서 가장 길게 지속되는 숫자들의 길이를 반환하면 됩니다. 1,2,3,4 이런식으로 지속되는 경우를 찾는 것이고 중간에 중복 값이 들어있어서는 안됩니다. 배열 안에서 지속되는 숫자의 연속이 두번 이상으로 나타날 수 있기에 잘 고려해보아야 합니다.

풀이

실행시간, 메모리 전부 최악이라 풀었다고 하기도 뭣하지만,, 일단 지금 당장 생각난 풀이가 이 방법밖에 없어서 올려두기로 하였습니다.

 

1. 배열 길이가 0이거나 1인 경우 각각 0과 1로 반환하여 쓸모 없는 계산을 줄입니다.

2. 어차피 숫자가 중복되는 경우는 연속하다고 보지 않기 때문에 nums를 중복제거한 후 정렬합니다.

3. nums를 돌면서 현재 요소의 +1한 값이 바로 다음 요소와 같다면 연속하는 경우이기에 count를 +1 합니다.

4. count가 max를 넘어가는 경우 max값을 count로 저장해줍니다.

5. 만약 중간에 연속이 끊긴 경우, nums[i] +1 == nums[i+1]이 아닌 경우 count를 다시 1로 초기화 합니다

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if len(nums) == 0: return 0
        if len(nums) == 1: return 1
        nums = sorted(set(nums))
        max = 1
        count = 1
        for i in range(0,len(nums)-1):
            print(i, count,max)
            if nums[i] + 1 == nums[i+1] :
                count += 1
                if count > max:
                    max = count
            else:
                count = 1
        return max