LeetCode [128]: Longest Consecutive Sequence

📌 LeetCode [128]: Longest Consecutive Sequence

🔗 문제 링크

---

문제 설명 📄

정수 배열 nums가 주어질 때, 배열에서 연속적인 정수로 이루어진 가장 긴 부분 수열의 길이를 반환하는 문제입니다. 연속적인 정수는 반드시 배열 내에서 이어져 있지 않아도 됩니다.

---

문제 접근 방식 📋

1. 연속 범위 확장:
   • 각 숫자를 기준으로 연속적인 숫자(left, right)를 양쪽으로 확장하여 가장 긴 연속 수열을 계산합니다.
2. 중복 처리 방지:
   • pattern 딕셔너리를 사용하여 이미 방문한 숫자를 추적해 중복 계산을 방지합니다.

---

Solution 💻

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        pattern = {i: 1 for i in nums}
        answer = []

        for i in nums:
            result = 1
            if pattern[i] == 1:
                pattern[i] = 0
                left = i - 1
                right = i + 1
                while left in pattern or right in pattern:
                    if left in pattern:
                        result += 1
                        pattern[left] = 0
                        left -= 1
                    if right in pattern:
                        result += 1
                        pattern[right] = 0
                        right += 1
                answer.append(result)

        return max(answer) if answer else 0

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n)
  • 각 숫자는 딕셔너리를 통해 한 번만 처리됩니다.
• 공간 복잡도: O(n)
  • pattern 딕셔너리로 추가 공간 사용.

---

리팩토링 🛠️

개선된 코드

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

        pattern = set(nums)
        max_length = 0

        for num in nums:
            if num - 1 not in pattern:
                current_length = 1
                current_num = num

                while current_num + 1 in pattern:
                    current_num += 1
                    current_length += 1

                max_length = max(max_length, current_length)

        return max_length

리팩토링 코드의 차이점

1. set 사용:
   • 딕셔너리 대신 set으로 중복 제거와 효율적인 탐색 수행.
2. 불필요한 리스트 제거:
   • 최대값을 바로 갱신하여 메모리 사용을 줄임.
3. 더 간결한 로직:
   • num - 1이 없는 숫자를 기준으로 연속 수열을 시작하여 탐색 범위를 최소화.

---

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n)
  • 모든 숫자는 set을 통해 한 번만 방문.
• 공간 복잡도: O(n)
  • set을 저장하는 데 추가 공간 사용.

---