128. Longest Consecutive Sequence ☆★★★★★★★★★

128. Longest Consecutive Sequence

 

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

 

 

기본적으로 정렬을 하면, => 시간 복잡도 O(n log n)

 

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

 

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

 

이 코드는 정렬 없이 연속된 수열의 최대 길이를 O(n) 시간 복잡도로 구하는 최적화된 방법입니다.

아래에 주석을 추가해서 한 줄씩 설명드릴게요:

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        """
        정렬 안 된 숫자 리스트에서
        연속된 숫자의 최장 길이를 O(n) 시간 복잡도로 구하는 함수
        """

        longest = 0

        # 중복 제거 및 탐색 속도 향상을 위한 set 사용 (O(1) 조회 가능)
        nums_set = set(nums)

        # 모든 숫자에 대해 반복
        for num in nums:
            # num-1이 존재하지 않으면, num은 시작점일 가능성이 있음
            if num - 1 not in nums_set:
                length = 1  # 현재 시퀀스 길이 초기화
                # num+1, num+2, ... 계속 존재하면 길이 증가
                while num + length in nums_set:
                    length += 1
                # 최대 길이 갱신
                longest = max(longest, length)

        return longest

---

예시:

입력: [100, 4, 200, 1, 3, 2]
→ 연속 수열 [1, 2, 3, 4] → 길이 4 반환

---

요약:

• 중복 제거와 시작점 판별을 통해 불필요한 탐색을 줄였고
• O(n) 시간 복잡도로 실행됨 (set 조회는 평균적으로 O(1))

사실 사용하신 코드는 이론적으로 O(n) 맞습니다.
하지만 for num in nums: 루프에서 num - 1 not in nums_set를 확인하는 방식이
중복된 숫자가 많을 때, 또는 nums 리스트에 중복이 잔뜩 들어 있을 경우에는
실제로는 O(n^2) 가까운 성능 저하가 발생할 수 있습니다.

문제 원인 요약:

• nums 리스트에는 중복 숫자가 들어 있을 수 있고,
• for num in nums:는 nums_set이 아닌 원래 nums를 기준으로 순회하므로,
• 같은 시작점을 여러 번 체크하게 됩니다.

---

⏱ 해결 방법:

리스트 nums 대신, 중복이 제거된 nums_set 자체를 순회하도록 수정하면 됩니다.

 

✅ 최종 코드

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        """
        정렬 안된 숫자 리스트를 주고
        연속된 숫자 시퀀스 길이 구하기.
        근데, 시간 복잡도가 O(n) 이 되어 야 
        """
        # 
        # 
        longest = 0
        nums_set = set(nums)
        """
        for num in nums: 를 => for num in nums_set: 로 수정하면 
        시간제한에 안걸림
        """
        for num in nums_set:
            # 시작점
            if num - 1 not in nums_set:
                length = 1
                while num + length in nums_set:
                    length +=1
                longest = max(longest, length)

        return longest

 

✅ 유니온 파인드 사용

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0

        par = {}
        # rank = {}
        size = {}  # 각 루트가 대표하는 집합의 크기
        set_nums = set(nums)  # O(1) 조회를 위해 set 사용

        # for n in nums:
        for n in set_nums: # 중복 제거된 값만 사용
            par[n] = n
            # rank[n] = 0 
            size[n] = 1  # 각 노드는 자기 자신만 포함한 크기 1로 시작
        
        def find(n):
            p =par[n]

            while p != par[p]:
                par[p] = par[par[p]]
                p = par[p]
            return p
        
        def union(n1, n2): # (size 기준으로 병합)
            p1, p2 = find(n1), find(n2)

            if p1 == p2:
                return False

            # 더 큰 쪽으로 병합
            if size[p1] > size[p2]:
                par[p2] = p1
                size[p1] += size[p2]
            else:
                par[p1] = p2
                size[p2] += size[p1]
            return True

        # 인접한 숫자 연결 (num과 num+1)
        for n in nums:
            if n+1 in nums:
                union(n, n+1)
        
        # print(size)
        # print([size[find(num)] for num in nums])
        # print([size[num] for num in nums])
        
        # 가장 큰 그룹의 size 반환
        return max(size[num] for num in nums)

 

https://youtu.be/P6RZZMu_maU