[LeetCode] 128. Longest Consecutive Sequence

말하는 감자·2024년 11월 6일
Array ListHash Tablebrute forceleetcodepythonsetsorting리스트리트코드배열정렬집합코딩테스트코딩테스트 준비파이썬해시 테이블
1

LeetCode

목록 보기
4/32
post-thumbnail

오늘 문제는 정말 배울것이 많다고 느낀 문제입니다. 어떤 문제인지 살펴보겠습니다.

1. 오늘의 학습 키워드

  • Array List
  • Hash Table
  • Sorting
  • Set

2. 문제: 128. Longest Consecutive Sequence

Description

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.

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is[1, 2, 3, 4]. Therefore its length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Constraints:

  • 0 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

3. 문제 풀이

정렬 되지 않은 정수 배열 nums 이 주어졌을 때, nums 에서 연속된 수의 갯수를 구하는 문제입니다.

문제를 차근차근 접근 해보겠습니다.

Step1. 문제 이해하기

  • Input:
    1. 정렬 되지 않은 정수 배열 nums 이 입력으로 주어집니다. 이 배열의 길이는 00부터 10510^5 입니다.
    2. 이를 통해 알 수 있는 것은 정수 배열 nums 이 빈 리스트일수도 있다는 점입니다.
    3. 또한, O(n2)O(n^2)보다 효율적인 시간 복잡도로 알고리즘을 구성해야 합니다.
    4. 여기서 n은 정수 배열 nums 의 길이가 될 것으로 예상됩니다.
    5. nums[i] 의 크기가 −109-{10}^9와 109{10}^9 사이라는 것은 int형, 즉 정수형의 값이라는 것을 의미합니다.
  • Output:
    • 연속됫 수의 개수(길이)
  • Examples:
    • Example 2에서 정수 0이 중복됩니다. 이것을 포함하지 않고 연속적인 값의 개수를 반환합니다.

Step2. 접근 방법

이전 Step1에서 input과 output을 제약 조건과 함께 분석을 진행했습니다. nums 는 정수 배열로서 빈 리스트 일수도 있고, 완성되는 알고리즘의 시간 복잡도는 O(n2)O(n^2)보다 작은 O(nlogn)O(nlogn), O(n)O(n)이면 됩니다.

그런데, 문제 마지막 문장에서 O(n)O(n) 시간 복잡도로 알고리즘을 구성하라고 나와있습니다.

하지만 이 문제는 정수 배열을 입력으로 사용하기 때문에 완전 탐색을 먼저 생각해볼 수 있습니다. 완전 탐색으로 먼저 알아보겠습니다.

첫번째 예시를 예로 진행해보겠습니다.

  • nums = [100, 4, 200, 1, 3, 2]
  • nums 배열의 각 요소들을 모두 탐색합니다. 아래 그림처럼 빨간색 원이 탐색을 의미합니다.
  • 이러한 탐색은 nums 배열을 for문을 돌면서 연속적인 값이 있는지 판단하는 in 연산자를 사용합니다.
    • 100의 연속적인 값, 101은 없으므로 넘어갑니다.
    • 4의 연속적인 값, 5는 없으므로 넘어갑니다.
    • 200도 넘어갑니다.

  • 그런데 1, 3, 2는 연속적인 값이 보이네요? 다음과 같습니다.

  • [100, 4, 200, 1, 3, 2]에서 1의 연속적인 값은 2입니다. 또 2에서 연속적인 값은 3, 3에서 연속적인 값은 4입니다.
  • 3, 2일때도 확인해보겠습니다.

  • 이렇게 nums 의 반복문을 한 번 돌 때, in 연산자를 통해 next값(연속적인 값)을 찾는 과정 O(n)O(n)이 필요하며, next가 연속적으로 있다면 이것또한 n번 반복하므로, 완전 탐색의 시간복잡도는 O(n3)O(n^3)이 됩니다.

그런데!! 여기서 충분히 시간을 줄일 수 있을것으로 보입니다!!

  1. in 연산자
    1. 리스트에서 in연산자의 시간복잡도는 O(n)O(n)이지만 hash table, set에서는 O(1)O(1)입니다.
  2. 조건을 통해 중복되는 탐색 제거
    1. [100, 4, 200, 1, 3, 2], [100, 4, 200, 1, 3, 2], [100, 4, 200, 1, 3, 2]에서 next(연속적인)값을 찾는 행동이 반복됩니다.
    2. 그런데 살펴보시면, 탐색을 시작하는 값보다 작은(이전) 값이 없을 때만 탐색을 진행한다면, 중복을 제거할 수 있게 됩니다.
    3. 3과 2보다 작은 값은 존재하지만 1보다 작은 값은 존재하지 않습니다. 따라서 1일때만 next값을 찾는것입니다.

이렇게 된다면 O(n3)O(n^3)에서 O(n)O(n)의 시간복잡도로 구현을 할 수 있게 됩니다.

지금까지 완전 탐색으로 출발해서 더 효율적으로 구성하기 위해 자료 구조를 변형하였습니다. 그런데 또 다른 방법도 생각해봐야 합니다. 이 문제는 정수 배열 nums 이 주어졌습니다. 이 배열은 정렬이 되어 있지 않다고 했습니다. 이렇게 배열 리스트가 주어지면 정렬 알고리즘을 생각해보는 것도 코드를 구현하기 전에 좋은 방법입니다.

정렬 알고리즘의 시간 복잡도는 O(nlogn)O(nlogn)입니다. 정렬을 먼저 진행하면 연속적인 값을 찾는데 훨씬 수월할 것으로 보입니다. next(연속적인)값을 찾는 행위가 없어지기 때문에 전체 시간복잡도가 O(nlogn)O(nlogn)이 될것으로 예상됩니다.

이제 코드를 구현해보겠습니다.

Step3. 코드 설계 및 구현

코드를 설계하기 전에 이전 step에서 꼭 짚고 넘어가야 하는 조건은 다음과 같습니다.

  1. nums 배열은 빈 리스트 일 수 있습니다.
  2. nums 배열에서 같은 값이 나오면 이것은 연속적인 값의 개수에 포함 되지 않습니다.

Brute Force 풀이

class Solution(object):
    #1. brute force
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        longest = 0 
        for num in nums:
            length = 1
            while num + length in nums:
                length+=1
            longest = max(length,longest)
        return longest

코드 설명:

이 방식은 nums의 각 원소에 대해 연속된 값을 가지는 시퀀스를 찾기 위해 완전 탐색을 사용합니다. 각 숫자에서 시작하여 그 숫자에 1씩 증가한 값이 nums에 있는지 확인하며, 이를 통해 연속된 길이를 계산합니다.

  • longest는 현재까지 찾은 가장 긴 연속 시퀀스의 길이를 저장합니다.
  • length는 각 숫자에서 시작하여 연속된 길이를 측정하는 변수입니다.
  • 이중 for와 while문으로 인한 O(n3)O(n^3) 시간복잡도를 가지므로, 성능은 좋지 않으며, 실제로도 Time Limit Exceeded 오류가 발생합니다.

시간 복잡도: O(n3)O(n^3)

결과:

https://leetcode.com/problems/longest-consecutive-sequence/submissions/1444587025

예상대로 Time Limit 초과가 나옵니다.

Hash Table 풀이

class Solution(object):
# 2. Hash Table
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        longest = 0
        hash_table = {}
        for num in nums:
            hash_table[num] = 1
        
        for num in hash_table:

            if num - 1 not in hash_table:
                cnt = 1
                while num + cnt in hash_table:
                    cnt += 1

                longest = max(longest,cnt)
        return longest

코드 설명:

해시 테이블을 사용해 모든 숫자를 key로 저장하고, 각 숫자에서부터 연속된 시퀀스를 찾습니다.

  • longest는 가장 긴 연속 시퀀스의 길이를 저장합니다.
  • num - 1이 해시 테이블에 없을 경우만 시퀀스를 시작합니다. 즉, 현재 숫자가 시퀀스의 시작인 경우에만 다음 숫자를 찾기 위해 num + cnt가 해시 테이블에 존재하는지를 확인하여 cnt를 증가시킵니다.
  • 중복된 탐색을 줄일 수 있기 때문에, 전체적인 시간 복잡도는 O(n)O(n)로 개선됩니다.

시간 복잡도: O(n)O(n)

결과:

https://leetcode.com/problems/longest-consecutive-sequence/submissions/1444590364

Hashtable에서 value는 사용하지 않기 때문에 Set 자료형을 사용해도 됩니다.

Set 풀이

class Solution(object):
# Set
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        longest = 0
        nums = set(nums) # O(n)

        for num in nums: # O(n)
            if num - 1 not in nums:
                cnt = 1
                while num + cnt in nums:
                    cnt += 1
                longest = max(longest,cnt)
        return longest

코드 설명:

해시 테이블 대신 Set을 활용하여 중복된 값을 자동으로 제거하고, 각 숫자에서 시퀀스를 시작합니다.

  • 먼저 Set 자료형을 통해 중복된 값을 제거하여 리스트의 크기를 줄입니다.
  • 이후 num - 1이 없는 경우(즉, 시퀀스의 시작이 되는 숫자인 경우)만 while문을 통해 연속된 숫자를 찾아갑니다.
  • 이 방식도 O(n)O(n)의 시간 복잡도를 가지며, 메모리 사용을 최소화할 수 있습니다.

시간 복잡도: O(n)O(n)

결과:

https://leetcode.com/problems/longest-consecutive-sequence/submissions/1444591867

정렬 풀이

class Solution(object):
# 정렬
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        nums.sort()
        longest = 0
        length = 1

        for i in range(len(nums)-1):
            if nums[i] == nums[i+1]:
                continue
            
            if nums[i] + 1 == nums[i+1]:
                length += 1
            
            else:
                longest = max(length,longest)
                length = 1
        
        longest = max(length,longest)
        return longest

코드 설명:

nums 배열을 정렬한 후 인접한 두 수가 연속된 숫자인지를 확인하여 연속된 시퀀스의 길이를 찾는 방식입니다.

  • 정렬된 상태에서 연속된 숫자인지 확인하므로 중복 탐색 없이 시퀀스를 파악할 수 있습니다.
  • nums[i] + 1 == nums[i + 1] 조건이 참일 때 length를 증가시키고, 연속되지 않은 경우에는 longest 값을 갱신하고 length를 초기화합니다.
  • 정렬의 시간 복잡도가 O(nlogn)O(nlogn)이므로, 대규모 데이터에서는 해시 테이블이나 셋 방법보다 성능이 떨어질 수 있습니다.

시간 복잡도: O(nlogn)O(nlogn)

결과:

https://leetcode.com/problems/longest-consecutive-sequence/submissions/1444600581

4. 마무리

이번 문제는 정렬되지 않은 배열에서 연속된 값의 시퀀스를 찾는 문제였습니다. 다양한 접근 방식을 통해 성능을 최적화할 수 있었고, 특히 해시 테이블과 셋을 사용하여 O(n)O(n)의 시간 복잡도를 달성할 수 있었습니다. 이를 통해 단순한 완전 탐색보다 훨씬 효율적인 방법으로 문제를 해결할 수 있었습니다.

문제를 해결하며 해시 테이블과 셋을 활용해 중복된 요소를 빠르게 처리하는 방법, 그리고 연속적인 값 탐색을 위한 조건 설정의 중요성을 확인할 수 있었습니다. 이러한 경험은 다양한 자료 구조를 활용하여 성능을 최적화하는 데 유용할 것입니다.

이번 문제를 통해 정렬과 해시 테이블을 통한 다양한 문제 해결 방법을 학습할 수 있었으며, 최적화 관점에서 접근 방식을 선택하는 중요한 경험이 되었습니다.

전체 코드는 다음 링크에서 확인할 수 있습니다.

읽어주셔서 감사합니다!!

계속 발전하는 개발자가 될거야!!

profile
말하는 감자
할 수 있다
이전 포스트

[LeetCode] 1. Two Sum

다음 포스트

[LeetCode] 20. Valid Parentheses

0개의 댓글