(Leet Code JS)Longest Consecutive Sequence

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

Longest Consecutive Sequence - LeetCode

Union-Find와 Map을 활용

parent라는 map을 선언.

nums[i]를 순회하면서 key와 value를 모두 자기 자신인 nums[i]로 초기화한다.

 

이후 연속된 수의 부모를 하나로 합치는 작업을 진행.

nums[i]를 순회하면서 unionParent() 함수를 실행한다.

unionParent 함수는 x를 매개변수로 받는데,

x + 1의 부모가 parent에 존재하는지 확인한다.

 

이를 pp라는 변수에 저장하며,

만약 pp가 undefined라면 x + 1의 부모가 자기 자신(연속된 숫자가 더 이상 없다)이기 때문에 x를 리턴.

그렇지 않다면 연속된 숫자가 존재하다는 뜻이 되기 때문에, x에는 pp에 해당하는 수를 갱신시킨다.

이때, dfs 형태로, x + 1의 부모도 존재할 수 있기 때문에 x를 key로, unionParent(pp)를 value로 저장한다.

이렇게 하면 value에는 언젠가 최상위 부모를 리턴하기 때문에 자동으로 연속된 숫자의 최대값을 저장할 수 있다.

 

마지막으로 다시 nums[i]를 순회한다.

parent에서 nums[i]를 key로 가지는 value를 가져온다.

만약 value가 없다면 0으로 저장.

value와 nums[i]의 차를 절대값으로 바꾼 후, + 1을 한 결과값이 연속된 숫자의 개수다.

이를 answer와 비교하여 계속 갱신해주면 된다.

const longestConsecutive = (nums) => {
    const parent = new Map();
    const {length} = nums;
    let answer = 0;
    
    const unionParent = (x) => {
        const pp = parent.get(x + 1);
        
        if(pp !== undefined){
            parent.set(x, unionParent(pp));
            
            return parent.get(x);
        } else{
            return x;
        }
    }
    
    // initialize
    for(let i = 0; i < length; i++){
        parent.set(nums[i], nums[i]);
    }
    
    // union
    for(let i = 0; i < length; i++){
        unionParent(nums[i]);
    }
    
    // find
    for(let i = 0; i < length; i++){
        const val = parent.get(nums[i]) || 0;
        const count = Math.abs(nums[i] - val) + 1;
        
        answer = answer < count ? count : answer;
    }
    
    return answer;
};