[LeetCode] 128. Longest Consecutive Sequence

😎풀이

Set 자료형을 활용하여 중복되는 숫자를 제거하고 순회하며 O(n)의 시간 복잡도로 처리 가능한 문제이다.

풀이 프로세스는 다음과 같다.

1. 숫자의 시작점인지 확인한다. (Set내에 현재 숫자 -1 의 숫자가 있는지 확인)
2. 다음 숫자가 있을 때까지 연속되는 횟수를 카운트 하며 확인한다.
3. 최댓값을 갱신한다.

function longestConsecutive(nums: number[]): number {
    if(!nums.length) return 0
    let longest = 1
    const numSet = new Set(nums)

    for(const num of numSet) {
        // 이 숫자가 시작점인지 확인
        if(numSet.has(num - 1)) continue

        let current = num
        let curLen = 1
        // 다음 숫자가 있는한 반복
        while(numSet.has(current + 1)) {
            current += 1
            curLen += 1
        }
        // 최댓값 갱신
        longest = Math.max(longest, curLen)
    }

    return longest
};