[LeetCode 해석 및 풀이] 128. Longest Consecutive Sequence

LeetCode 문제 해석 및 풀이 방법

 

문제 128. 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.

 

한글

정렬되있지 않은 정수 배열 nums가 주어지면 가장 긴 연속된 수열의 길이를 구하시오

반드시 O(n)으로 알고리즘을 작성해여야 합니다.

 

제한조건

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

 

입출력 예

입력	출력
nums = [100,4,200,1,3,2]	4
nums = [0,3,7,2,5,8,4,6,0,1]	9

 

 

해답 및 해설

파이썬 (Python)

우선 첫 번째로 다음과 같이 딕셔너리에 가장 긴 수열의 길이를 저장해두고, 숫자가 추가되면 저장된 수열 길이를 업데이트 하게 작성하였으나, 시간 통과를 하지 못 했다. 아마 수열 길이를 전부 업데이트 하는 과정이 오래 걸린 듯 하다.

class Solution:
    def __init__(self):
        self.count = defaultdict(int)
        self.max = 0

    def update(self, num:int):
        if self.count[num] != 0: return

        length = self.count[num-1] + self.count[num+1] + 1
        self.count[num] = length
        if length > self.max: 
            self.max = length

        if self.count[num-1] != 0: 
            self.update_left(num-1, length)
        if self.count[num+1] != 0: 
            self.update_right(num+1, length)

    def update_left(self, num:int, length:int):
        self.count[num] = length
        if self.count[num-1] != 0: 
            self.update_left(num-1, length)

    def update_right(self, num:int, length:int):
        self.count[num] = length
        if self.count[num+1] != 0: 
            self.update_right(num+1, length)

    def longestConsecutive(self, nums: List[int]) -> int:
        for num in nums:
            self.update(num)

        return self.max

 

 

그래서 연속된 수열의 최댓값에는 최솟값을, 최솟값에는 최댓값만 저장해두고, 수열의 중간에 있는 숫자에는 중간에 있는 값이라는 표시를 저장해 중복을 막는 방식으로 했더니 통과하였다.

class Solution:
    def __init__(self):
        self.count = {}
        self.longest = 0

    def update(self, num:int):
        if num in self.count: return

        min = max = num
        if num-1 in self.count:
            min = self.count.get(num-1)
            self.count[num-1] = 'mid'
        if num+1 in self.count:
            max = self.count.get(num+1)
            self.count[num+1] = 'mid'

        self.count[num] = 'mid'
        self.count[min] = max
        self.count[max] = min

        if self.longest < max-min+1:
            self.longest = max-min+1

    def longestConsecutive(self, nums: List[int]) -> int:
        for num in nums:
            self.update(num)

        return self.longest

 어떤 숫자를 입력받았을 때, 해당 숫자보다 1 작은 숫자가 저장되어 있다면, 이전에 있던 수열중 하나의 최댓값일테니 최솟값을 해당 숫자에 저장되있는 최솟값으로 설정해준다. 또 1 큰 숫자가 저장되어 있다면, 이전에 있던 수열 중 하나의 최소값일테니 최대값을 해당 숫자에 저장되어있는 최대값으로 설정해준다. 그리고 중간 숫자들은 모두 'mid'라 표시한 후 최대에는 최소를, 최소에는 최대를 다시 넣어준다. 이를 반복하여 가장 긴 수열 길이를 찾는다.

 

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

        while nums:
            n = nums.pop()
            down = n - 1
            down = n + 1

            while down in nums:
                nums.remove(down)
                down -= 1
           down += 1

            while up in nums:
                nums.remove(up)
                up += 1
            up -= 1

            res = max(res, up - down + 1)

        return res

 

하지만 내 방법 말고 더 나은 방법이 있었다. 우선 주어진 배열을 집합으로 바꾸어 중복을 없애준 뒤, 한 숫자를 빼서 고르고 해당 숫자와 1차이 나는 숫자들을 계속 찾아나가 최댓값과 최솟값을 찾는다. 이렇게 해서 집합의 모든 숫자를 없앨 때까지 반복하는 방법이었다. 

내가 짠 방법은 숫자들을 계속 입력받을 경우, 맨 아래 방법은 입력된 숫자가 고정되어 있는 경우 유용할 듯 싶다.