📕문제

[LeetCode] 128. Longest Consecutive Sequence

문제 설명

정렬되지 않은 숫자 리스트에서 가장 긴 연속된 숫자의 개수를 구하는 문제다.
예를들어 [100,4,200,1,3,2] 가 주어졌을 때 가장 긴 연속된 숫자는 [1,2,3,4] 이므로 정답은 4다.

---

📝풀이

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0
        nums.sort()
        result = [1]
        prev, cursor = nums[0], 0
        for num in nums:
            if num == prev:
                continue
            elif num == prev + 1:
                result[cursor] += 1
            else:
                cursor += 1
                result.append(1)
            prev = num
        return max(result)

• nums가 빈 리스트면 0을 반환한다.
• nums를 정렬한다.
• 정렬된 nums에서 연속된 숫자를 카운트 하며 값을 업데이트 한다.
• 연속된 숫자의 개수가 저장된 result에서 가장 큰 값을 반환한다.

코드를 짜고보니 리스트에서 중복 요소를 제거하면 조건문을 하나 줄일 수 있을 것 같아 코드를 수정해보았다.

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0
        nums = list(set(nums))
        nums.sort()
        result = []
        prev, cursor = nums[0], -1
        for num in nums:
            if num == prev + 1:
                result[cursor] += 1
            else:
                cursor += 1
                result.append(1)
            prev = num
        return max(result)

• nums를 set으로 형변환 후 다시 리스트로 변환해 중복 요소를 제거한다. 이후 정렬한다.

 

첫번째 풀이 - 중복 제거 X	두번째 풀이 - 중복 제거 O

실행시간은 미세하게 줄었지만 공간복잡도가 오히려 늘어났다..