⭐️ LeetCode 알고리즘 풀이 (with Python)

# Longest Consecutive Sequence

[Quetion]

LeetCode 128. Longest Consecutive Sequence

📌 접근법

[문제 이해]

• 리스트 내에서 연속된 수의 최대 개수 반환

Hashmap을 활용하는 문제이지만 우선 바로 생각나는대로 풀어보았다.
생각의 흐름은 다음과 같다.

• nums 리스트의 중복을 제거
• 중복 제거한 nums 리스트를 정렬
• 리스트의 첫 값을 변수에 저장, 카운트 변수와 카운트 리스트 선언
• 리스트의 길이만큼 반복
• 저장한 변수 + 1이 다음 순서의 값과 같으면 카운트 + 1
• 아니면 카운트 리스트에 카운트 추가, 카운트 = 0
• 변수는 비교한 리스트 값으로 재정의

💻 구현

class Solution:
    def longestConsecutive(self, nums):
        # nums가 없으면 0
        if not nums:
            return 0
        
        # 중복제거 & 정렬
        nums = sorted(set(nums))
        n = nums[0]
        
        # 연속된 수의 개수 저장
        count = 0
        
        # 연속이 끊겼을 때, 연속되었던 수 저장
        max_c = []
        
        for i in range(1,len(nums)):
            if n+1 == nums[i]:
                count+=1
            else:
                max_c.append(count+1)
                count=0
            n = nums[i]
        
        max_c.append(count+1)
        max_c.sort()
        return max_c[-1]

Runtime: 335ms | Memory: 30.9MB
LeetCode 코드 중 Runtime 99%, Memory 87% 해당하는 결과

📌 로직 핵심

• 주어진 리스트의 중복을 제거하고 정렬
• 연속되는지 확인 후 연속된 개수 세기
• 연속이 끊기면 현재까지 연속된 개수를 리스트에 저장
• 모두 연속된 경우를 대비하여 반복 후, 연속된 개수를 다시 추가
• 연속된 개수가 담긴 리스트를 정렬하면 가장 큰수는 마지막 값

📝 Longest Consecutive Sequence 회고

• 해당 코드의 시간복잡도는 nums의 중복을 제거하여 O(nlogn)이고 최악은 중복이 없는 경우의 O(N)이다. 공간복잡도는 중복을 제거후, 정렬된 새로운 리스트를 생성하는 과정에서 O(N)이다.

• 현재 코드에서는 max_c 리스트에 연속되는 개수를 저장하는 방법으로 최대 연속 개수를 판단하지만, max()함수를 활용해서 하나의 변수를 최대값으로 갱신하는 것으로도 결과를 도출할 수 있을 것이라 생각했다.

• 다른 솔루션들도 중복을 제거, 정렬하는 방법으로 접근을 했고, 굳이 dictionary 자료구조를 활용한 솔루션은 거의 없던 것 같다. 현재 코드가 성능도 어느정도 좋게 나왔고, 코드 흐름도 파악하기 쉽다고 생각하여 추가 변경은 하지 않았다.