leetcode : Longest Consecutive Sequence

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

Longest Consecutive Sequence - LeetCode

 

정렬하면 O(N log N)으로 쉽게 풀 수 있다. 하지만..!? O(N)으로 풀어야 된다는 조건이 명시되어 있다. 생각해보면 이 문제에서는 특정 숫자에 대해 +1, -1한 숫자가 array에 존재하는지에 대한 정보만 있으면 된다. 하지만 정렬의 경우 한 요소당 최소 log N개의 요소와의 비교 정보가 필요하다. 그니까 정렬은 불필요한 정보까지 계산하고 있다는 것이다.

 

이 문제는 disjoint set (union-find)를 이용하면 쉽게 풀 수 있다.

모든 요소를 disjointset에 넣어놓고 나보다 +1,-1 한 요소가 있으면 union을 진행해주면 된다. 그리고 union하면서 현재 서로소집합의 크기가 어느정도인지 카운트 해주면 정답을 쉽게 구할 수 있다.

class DisjointSet:
    def __init__(self):
        self.dset = {}
        self.count = {}
        self.longest_consecutive = 1
        
    def add(self, e):
        self.dset[e] = e
        self.count[e] = 1
        
    def union(self, e1, e2):
        h1 = self.find(e1)
        h2 = self.find(e2)
        
        root = min(h1,h2)
        sub = max(h1,h2)
        self.dset[sub] = root
        
        if root != sub:
            self.count[root] += self.count[sub]
            self.longest_consecutive = max(self.longest_consecutive, self.count[root])
        
            
    def find(self, e):
        if self.dset[e] != e:
            self.dset[e] = self.find(self.dset[e])
            return self.dset[e]
        else:
            return e
        
    def exists(self, e):
        return e in self.dset.keys()
    
    def longestConsecutive(self):
        return 0 if len(self.dset.keys()) == 0 else self.longest_consecutive

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        maxlen = 1
        dset = DisjointSet()
        
        for num in nums:
            dset.add(num)
        
        for num in nums:
            if num != - 10**9 and dset.exists(num - 1):
                dset.union(num - 1, num)
            if num != 10**9 and dset.exists(num + 1):
                dset.union(num, num + 1)
        
        return dset.longestConsecutive()

최적화가 좀더 필요해보인다.

일단 클래스로 만들었던걸 안에다 넣어볼까

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        maxlen = 1
        dset = {}
        counter = {}
        
        def find(e):
            if dset[e] == e:
                return e
            dset[e] = find(dset[e])
            return dset[e]
        
        def union(e1,e2):
            nonlocal maxlen
            
            h1 = find(e1)
            h2 = find(e2)
            
            if h1 < h2:
                dset[h2] = h1
                counter[h1] += counter[h2]
                maxlen = max(maxlen, counter[h1])
            elif h2 < h1:
                dset[h1] = h2
                counter[h2] += counter[h1]
                maxlen = max(maxlen, counter[h2])
        
        for num in nums:
            dset[num] = num
            counter[num] = 1
        
        for num in nums:
            if num != - 10**9 and num - 1 in dset.keys():
                union(num, num - 1)
            if num != 10**9 and num + 1 in dset.keys():
                union(num, num + 1)
        
        return maxlen if nums else 0

여전히 썩..

 

counter 딕셔너리가 없어져야되나보다.

 

이쯤에서 다른 사람 풀이를 보자

public int longestConsecutive(int[] num) {
    int res = 0;
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int n : num) {
        if (!map.containsKey(n)) {
            int left = (map.containsKey(n - 1)) ? map.get(n - 1) : 0;
            int right = (map.containsKey(n + 1)) ? map.get(n + 1) : 0;
            // sum: length of the sequence n is in
            int sum = left + right + 1;
            map.put(n, sum);
            
            // keep track of the max length 
            res = Math.max(res, sum);
            
            // extend the length to the boundary(s)
            // of the sequence
            // will do nothing if n has no neighbors
            map.put(n - left, sum);
            map.put(n + right, sum);
        }
        else {
            // duplicates
            continue;
        }
    }
    return res;
}

이게 사람 발상인가? 어떻게 이런발상을 하지;;

hashmap 하나만 만들고 각 숫자가 포함된 그룹의 크기를 value에 기록한다.

n-1,n+1이 있다면 각각의 크기를 가져오고 합한뒤 +1 해주면 n이 union된 뒤의 합쳐진 크기를 구할 수 있다.

이제 이 계산 결과를 인접한 숫자에 퍼뜨려주는 파트가 기가맥힌데

map.put(n - left, sum);

map.put(n + right, sum);

이 발상, 진짜 말이 안된다 ㅋㅋㅋ 어떻게 이런생각을 했지.

예를 들어 1, 2를 map에 넣었다고 치자. 두 숫자는 한 그룹이고 그룹의 크기가 2니까 map은 다음과 같이 형성됐을거다.

1->2

2->2

이때 3이 들어오면 어떻게 될까? 3보다 작고 인접한 숫자가 2개 있으므로 left의 크기는 2, right의 크기는 0이다. 그 둘을 더하고 또 1을 더해주면 3.

1->2

2->2

3->3

근데 1,2,3은 이제 한 그룹으로 묶였으니까 1과 2도 ->3 이 되어야 한다. 이때 map.put(n - left, sum)이 실행된다.

map.put(3 - 2, 3);

1->3

2->2

3->3

아니 중간에 2는 안바뀌었잖아? 바뀔 필요가 없다. 어차피 1과 3이 이미 있기 때문에 key 2가 참조될 일이 없기때문ㅇ....

아니 이걸 어떻게 생각하냐고ㅁㄴ이라ㅓㅁㄴㄷ햐ㅓㅁㄴ이라ㅓㅁ니ㅏ험ㄴㅇㄹ

이런게 구글 인터뷰에서 나온다면 난 구글에 평생 못갈지도..

 

이걸 내 파이썬 코드로 구현해보고 결과를 살펴보자.

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        maxlen = 0
        dset = {}
        
        for num in nums:
            if num not in dset:
                left_size = dset[num-1] if num-1 in dset else 0
                right_size = dset[num+1] if num+1 in dset else 0
                
                my_size = left_size + right_size + 1
                maxlen = max(maxlen, my_size)
                
                dset[num] = my_size
                dset[num - left_size] = my_size
                dset[num + right_size] = my_size
                
        return maxlen

기가 차서 벙이찌네 진짜 ㅋㅋ

근데 메모리는 왜 8.6%밖에 안나왔을까? 또 다른 사람들은 얼마나 메모리를 적게 쓰길래?

 

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        longest = 0
        nums_set = set(nums)
        for n in nums:
            if (n - 1) not in nums_set:
                length = 1
                while (n + length) in nums_set:
                    length += 1
                longest = max(length, longest)
        return longest

 

오 이렇게 풀 수도 있네 ㄸ

나보다 작은 놈이 없으면 내 위로 몇명 있는지 세는거다. 똑똑한데?

 

역시 난 아직 멀었구나