[Leetcode] 128. Longest Consecutive Sequence

문제

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

풀이

혼자힘으로 풀지 못했고, discussion의 답을 확인하였다.

핵심은 set() 형변환을 통해 특정 숫자가 존재하는지 체크하는 in 연산을 할 때 O(1)이 되도록 하는 것이다.

처음에는 아래 코드의 시간복잡도가 O(N)을 넘어서 문제가 될거라 생각했으나 로직을 생각해봤을 때 O(N+N)이므로 O(N)이 유지된다.

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        ans = 0
        num_set = set(nums) # in, not in 연산을 O(1)로 처리하기 위해 set으로 형변환

        for num in num_set: # O(N)
            if (num-1) not in num_set: # 연속되는 수들의 첫 시작 숫자일 때
                now_len = 1
                while (num+now_len) in num_set:
                    now_len += 1
                ans = max(ans, now_len)
        
        return ans

• union find 기반의 풀이도 가능하다

find: 하나의 원소가 어떤 집합에 속해있는지를 판단하는 연산
union: 서로 다른 두 개의 집합을 하나의 집합으로 병합하는 연산

class Node:
    def __init__(self, val):
        self.val = val
        self.parent = self
        self.size = 1
    
class UnionFind:
        
    def find(self, node):
        if node.parent != node:
            node.parent = self.find(node.parent)
        return node.parent
    
    def union(self, node1, node2):
        parent_1 = self.find(node1)
        parent_2 = self.find(node2)
        if parent_1 != parent_2:
            parent_2.parent = parent_1
            parent_1.size += parent_2.size
        return parent_1.size
                
        
        
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        uf = UnionFind()
        nodes = {}
        max_size = 0
        for num in nums:
            if num not in nodes:
                node = Node(num)
                nodes[num] = node
                size = 1
                if num + 1 in nodes:
                    size = uf.union(node, nodes[num+1])
                if num - 1 in nodes:
                    size = uf.union(node, nodes[num-1])
                max_size = max(max_size, size)
                
        return max_size