[Leetcode] 128. Longest Consecutive Sequence_해설, 풀이, 설명

---

안녕하세요, HELLO

 

오늘은 Leetcode 알고리즘 문제 '128. Longest Consecutive Sequence'에 대해서 살펴보고자 합니다. 

 

알고리즘 문제, 코드, 해설 그리고 Leetcode에서 제공해준 solution 순서대로 정리하였습니다.

---

STEP 1. 'Longest Consecutive Sequence' 알고리즘 문제

 

STEP 2. 'Longest Consecutive Sequence' 코드(code)

 

STEP 3. 'Longest Consecutive Sequence' 해설

 

STEP 4. 'Longest Consecutive Sequence' solution

 

반응형

 

STEP 1. 'Longest Consecutive Sequence' 알고리즘 문제

 

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
You must write an algorithm that runs in O(n) time.

 

정렬되지 않은 정수 배열이 주어지면 가장 긴 연속 요소 시퀀스의 길이를 반환합니다.
O(n) 시간에 실행되는 알고리즘을 작성해야 합니다.

 

 

Constraints:

 

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

---

STEP 2. 'Longest Consecutive Sequence' 코드(code)

 

■ Runtime: 343ms Beats 75.67%
■ Memory: 30.82MB Beats 95.61%

 

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

        nums = sorted(nums)

        longest_sequence, temp_sequence = 1, 1

        for idx in range(len(nums) -1):
            if nums[idx+1] == nums[idx] +1:
                temp_sequence += 1
            elif nums[idx+1] == nums[idx] : continue
            else:
                longest_sequence = longest_sequence if longest_sequence > temp_sequence else temp_sequence
                temp_sequence = 1
        longest_sequence = longest_sequence if longest_sequence > temp_sequence else temp_sequence
        return longest_sequence

---

STEP 3. 'Longest Consecutive Sequence' 해설

 

연속된 숫자가 나오게 될 경우, 최대 연속적으로 나타난 횟수를 계산합니다.

이때, nums에 아무 값도 없는 경우는 0을, 그리고 1개 이상 있을 경우로 나눠서 판단합니다.

 

예시에 나와있듯이 [0,0,1] 처럼 동일한 숫자가 있는 경우에는 연속성이 끊겼다고 생각하지 않고, 이어서 횟수를 계산해야 합니다. 그리고 연속성이 끊기게 될 경우에는 이전까지 최대 연속 횟수랑 비교해서 업데이트 합니다. 

 

 

STEP 4. 'Longest Consecutive Sequence' solution

 

추가적으로, Leetcode에서 제공해준 solution 코드를 살펴보겠습니다.

 

■ Runtime: 4228ms Beats 25.26%
■ Memory: 31.80MB Beats 37.33%

 

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        num_set = set(nums)
        longest = 0

        for n in nums:
            if n - 1 not in num_set:
                length = 1

                while n + length in num_set:
                    length += 1
                
                longest = max(longest, length)
        
        return longest

---

■ 마무리

 

오늘은 Leetcode 알고리즘 문제 '128. Longest Consecutive Sequence'에 대해서 알아봤습니다.

좋아요와 댓글 부탁드리며,

오늘 하루도 즐거운 날 되시길 기도하겠습니다 :)

감사합니다.