[ leetcode 문제풀이 ] Longest Consecutive Sequence

Longest Consecutive Sequence - LeetCode

Longest Consecutive Sequence - LeetCode

(Longest Consecutive Sequence 문제는 위 링크에서 풀어보실 수 있습니다.)

 

 

 

 

< Longest Consecutive Sequence 문제 설명 >

 

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) 시간 내에 실행되는 알고리즘을 작성해야 한다.

 

다음 두 가지 출력 예시가 주어졌다.

 

 

주어진 제한 조건은 0 ≤ nums.length ≤ 10^5,  -10^9 ≤ nums[i] ≤10^9 이다.

 

 

 

 

---

< Longest Consecutive Sequence 문제 접근 >

 

가장 간단하게 생각할 수 있는 방법은 nums 배열을 정렬해 연속되는 숫자의 길이를 카운트 하는 것이 있겠지만, 정렬의 시간복잡도가 O(n log n)이므로 이 방법을 사용할 수 없을 것이다. 이 문제에서 related topics로 제시한 Union Find(Disjoint-set data structure)와 Hash Table을 활용한 알고리즘을 작성해보자.

 

Union Find를 어떻게 이 문제에 적용할 수 있을까?

 

먼저 nums의 원소라는 전체 집합을 어떤 서로소 집합으로 나타낼 수 있을지를 생각해보면 연속되는 수열끼리를 하나의 집합으로 생각할 수 있다. 이때 집합으로 합치는 Union의 적용을 nums[i]에 대해 nums[i]+1에 해당하는 수가 있으면 이 두 원소를 Union하도록 할 수 있을 것이다. 단, nums[i]에 대해 nums[i]+1(=nums[j])에 해당하는 값을 갖는 index j가 존재하는지의 탐색을 이진탐색을 사용하면 O(n)의 runtime을 만족하지 못하므로 Hash Table을 사용해 O(1)의 탐색 runtime을 갖도록 한다. 

 

이 같은 아이디어로 작성한 알고리즘은 다음과 같다. (Cpp 사용)

 

#include <unordered_map>
using namespace std;

struct Node{
    Node* parent;
    int rank = 0;
};
    
// this can be decreased to a constant amount memory
// by performing both passes in the same direction
// two passes - once to find the root, once to update pointers.
Node* Find(Node* x){
    Node* root = x;
    while(root->parent != root)
        root = root->parent;
     
    while(x->parent != root){
        Node* parent = x->parent;
        x->parent = root;
        x = parent;
    }
    return root;
}
    
// union by rank - ensure that trees do not become too deep
void Union(Node* x, Node* y){
    x = Find(x);
    y = Find(y);
       
    if(x == y) return;
       
    if(x->rank < y->rank){
        Node* temp = y;
        y = x;
        x = temp;
    }
        
    y->parent = x;
    if(x->rank == y->rank)
        x->rank += 1;
} 
    
int longestConsecutive(vector<int>& nums) {
    int n = nums.size();
    Node* Set = new struct Node[n];
    unordered_map<int, int> inverseNums;
        
    // MakeSet func.
    for(int i=0;i<n;i++){
        inverseNums[nums[i]] = i;
        Set[i].parent = Set+i;
    }
        
    for(auto elem : inverseNums){
        auto check = inverseNums.find(elem.first+1);
        if(check != inverseNums.end())
            Union(Set + inverseNums[elem.first], Set + inverseNums[elem.first+1]);
    }
       
    unordered_map<Node*, int> cnt;
    for(auto elem : inverseNums)
        cnt[Find(Set + inverseNums[elem.first])]++;
    
    int ans = 0;
    for(auto elem : cnt)
        ans = max(ans, elem.second);
        
    return ans;
} // runtime 106 ms (faster than 62.70 %), memory usage 33.3 MB (less than 7.58%)

 

inverseNums[nums[i]] = i 가 되도록 하는 hash table을 정의하고 inverseNums의 key(nums의 숫자들, consecutive sequence를 확인해야하는 숫자)에 대해 key+1을 key로 하는 쌍이 있는지를 찾는다.(O(1) runtime) 만약 존재하면 key에 해당하는 집합과 key+1에 해당하는 집합을 Union한다. (이때 탐색을 inverseNums의 key에 대해서 진행하므로 중복되는 nums의 숫자는 무시할 수 있다.)

 

그 후 key에 해당하는 Node의 root node를 key로 하는 새로운 hash table: cnt를 정의한다. 이 hash table의 value는 집합의 원소 수(= consecutive sequence의 길이)와 같다. hash table (cnt)를 돌면서 value의 최댓값(=longest consecutive sequence)을 리턴한다.

 

시간복잡도 분석(disjoint-set data structure wikipedia 내용)

The combination of path compression, splitting, or halving, with union by size or by rank, reduces the running time for m operations of any type, up to n of which are MakeSet  operations, to O(mα(n)).This is asymptotically optimal, meaning that every disjoint set data structure must use Ω(α(n)) amortized time per operation.

→ path compression 혹은 splitting, halving(Find function)과 union by size or by rank(Union function)의 조합을 사용하면 m회의 실행에서 O(mα(n))까지 runtime을 줄여준다. 이는 점근적으로 최적이며, 모든 서로소 집합 자료구조가 1회 실행 당 최소 α(n)의 시간을 소요함을 의미한다.

 

위 알고리즘의 경우 inverseNums에 대한 탐색이 최대 n회 발생하므로 time complexity 는 O(nα(n)). 이때 α(n)은 실질적으로 상수시간으로 취급할 수 있으므로 O(n)의 알고리즘이라 할 수 있다.