128. Longest Consecutive Sequence

128. Longest Consecutive Sequence

 

https://youtu.be/8sF5-yK2jsk?si=azgL_NMsGEf7q6pV

 

로직은 맞지만, 시간 제한에 걸림!! : 시간 복잡도 O(n^3)

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        """
        time: O(n^3): for + while + while 안에 in 조건문
        space: O(1)

        """
        # 초기화: 최장 연속 수열 길이를 저장할 변수
        longest = 0  # 최장 길이를 저장하기 위한 변수 초기화

        # 입력 배열의 각 숫자에 대해 반복
        for n in nums:  
            # 현재 숫자를 시작으로 연속된 수열의 길이를 측정
            length = 1  # 현재 숫자를 포함하여 최소 길이는 1로 설정
            
            # 현재 숫자 + length가 배열에 포함되는 동안 반복

            # in 은.. 선형탐색을 하면서 검색하므로.. 
            # loop 가 하나 더 있다고 생각하면 됨
            while n + length in nums:  
                length += 1  # 연속된 숫자가 있으면 길이를 증가
            
            # 최장 연속 수열 길이를 갱신
            longest = max(longest, length)  
            # 이전 최장 길이와 현재 연속 길이를 비교하여 더 큰 값을 저장
        
        # 최장 연속 수열 길이를 반환
        return longest

 

따라서, 정렬이 필요!!

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        """
        time: O(nlong(n))
        space: O(1)
        """
        if not nums: # 빈 리스트면 
            return 0

        """
        << 주의 >>
        Input: [1, 2, 0, 1]
        Sorted: [0, 1, 1, 2] => 따라서, 길이는 3임, 1의 중복은 1개로 쳐야 함
        """        
        nums.sort()
        longest = 0

        length = 1
        for i in range(len(nums)-1):
            # 동일 숫자가 2번 나오는거 체크
            if nums[i] == nums[i+1]:
                continue # length 증가시키지 않고, 다음 i로 넘어감

            if nums[i] +1 == nums[i+1]:
                length +=1
            else:
                longest = max(longest, length)
                length = 1

        # for 나올때 length 도 반영시켜줘야 하므로, 한번 더 필요!
        longest = max(longest, length)
        return longest

 

기본적으로 정렬을 하기때문에, 반영해서, 시간 복잡도 O(n log n)

 

문제에서 요구하는 것은, 시간 복잡도 O(n) 임 !!

 

1번째 코드에서, Set 을 사용하여. 속도 개선!

 

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        """
        time: O(n^3): for + 
                    [while + while 안에 in 조건문] <-- set 사용하면, 속도 개선
        개선된 코드 time: for O(n) + while O(n) => O(2n) => O(n)
            - O(n^2) 으로 보이지만, 자세히 살펴보면, 그렇지 않음!!
        """
        num_set = set(nums)

        # 초기화: 최장 연속 수열 길이를 저장할 변수
        longest = 0  # 최장 길이를 저장하기 위한 변수 초기화

        # 입력 배열의 각 숫자에 대해 반복
        for n in nums:  
            # n-1 값이 num_set에 있으면, 최초값이 될 가능성이 없으므로, skip 함 
            if n - 1 in num_set:
                continue

            # 현재 숫자를 시작으로 연속된 수열의 길이를 측정
            length = 1  # 현재 숫자를 포함하여 최소 길이는 1로 설정
            
            # 현재 숫자 + length가 배열에 포함되는 동안 반복

            # in 은.. 있더라도, **(set 사용하므로, 상수시간을 사용해서 탐색을 함)**
            # 따라서, 아래 while 문은 시간 복잡도가 O(n) 
            while n + length in num_set:  
                length += 1  # 연속된 숫자가 있으면 길이를 증가
            
            # 최장 연속 수열 길이를 갱신
            longest = max(longest, length)  
            # 이전 최장 길이와 현재 연속 길이를 비교하여 더 큰 값을 저장
        
        # 최장 연속 수열 길이를 반환
        return longest

 

최적화 코드

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        """
        time: O(n) 
        """
        num_set = set(nums)

        # 초기화: 최장 연속 수열 길이를 저장할 변수
        longest = 0  # 최장 길이를 저장하기 위한 변수 초기화

        # 입력 배열의 각 숫자에 대해 반복
        for n in nums:  
            # n-1 값이 num_set에 있으면, 최초값이 될 가능성이 없으므로, skip 함 
            # n-1 값이 num_set에 없는 것들만 로직 계산
            if n - 1 not in num_set:
                length = 0
                while (n + length) in num_set:  
                    length += 1  # 연속된 숫자가 있으면 길이를 증가            
                # 최장 연속 수열 길이를 갱신
                longest = max(longest, length)          
        # 최장 연속 수열 길이를 반환
        return longest