[leetcode] 128. Longest Consecutive Sequence 시간복잡도 O(n) 풀이, 해설 (python)

문제 링크

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

Longest Consecutive Sequence - LeetCode

 

1차 풀이

O(n)을 목표로 풀다가, O(nlogn)으로 빠져버린 풀이이다.

중간에 정렬을 진행했기 때문에 O(nlogn), 그 후 for문에서 O(n) 총 O(n) + O(nlogn) = O(nlogn)이 되었다. 

 

class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
    
        result = 0 
        prev = None
        tempCount = 1
        
        nums.sort()
        for n in nums:
            # prev 이 초기화되어있거나 전 값과 동일한 경우 
            if prev == None or prev == n:
                prev = n
            # 연속된 경우 
            elif prev + 1 == n:
                prev = n 
                tempCount += 1 # 연속적인 경우 카운트 
            else:
                prev = n # 초기화 
                tempCount = 1
                
                
            result = max(result, tempCount) # 값 갱신 
      
        
        return result

 

2차 풀이 (해설 참고, 시간복잡도 O(n))

아래 유투브를 참고했다. 

https://www.youtube.com/watch?v=P6RZZMu_maU

아래 알고리즘의 경우 시간복잡도를 계산했을때, for문 안에 while 문이 있기 때문에 O(n^2) 아닌가 싶긴 했는데, 

이미 set로 바꾸었기 때문에 값이 있는지 검사할때 O(1)밖에 걸리지 않고, 

연속된 숫자배열 [1,2,3,4]가 있는 경우 2,3,4일때는 if조건문에 빠져서 검사를 안하고 1일때만 1->2->3->4 로 검사를 하기 때문에 결과적으로 O(n)의 시간복잡도가 걸리게 된다. 

longest = 0
numSets = set(nums)
for n in numSets:
    if n -1 in numSets:
        continue;
    else:
        t = n 
        tlengh = 1 
        while t + 1 in numSets:
            tlengh += 1 
            t = t + 1 

        longest = max(tlengh, longest)

return longest