풀이

정렬을 해서 풀면 간단하게 풀 수 있다.
하지만 문제에서 주어진 조건이 시간복잡도 O(N)으로 해결하라고 명시되있다.
정렬을 해서 풀이해도 통과는 되지만, O(NlogN)의 시간복잡도를 가질 것이다.
따라서 다른 방법을 생각해보게 되었고, 문제의 솔루션 부분을 참고하여 해시맵을 사용하여 문제를 해결하였다.

코드

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
    // map을 사용하여 key값으로 저장
    const map = new Map();
    for(let i=0; i<nums.length; i+=1){
        map.set(nums[i], true);
    }

    let longest = 0;
    map.forEach((value, key)=>{
        // 이 조건이 시간복잡도에 영향을 끼친다.
        // 앞에 숫자가 있는지 확인하여
        // 이미 길이를 찾은 부분인지 체크해줘야 타임아웃이 안나온다.
        if(!map.has(key-1)){
            let currentKey = key;
            let currentLength = 1;
            while(map.has(currentKey+1)){
                currentLength+=1;
                currentKey+=1;
            }
            if(currentLength>longest){
                longest = currentLength;
            }   
        }

    })

    return longest;
};

정리

맨 처음에 if(!map.has(key-1)) 이 조건을 안넣었다가 타임아웃이 발생하였다.
이미 검사한 부분인지 확인해야 하기 때문에 해당 조건이 필요하다.

출처

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