Longest Consecutive Sequence

💬 문제

[문제 링크]

정렬되지 않은 정수배열 nums
연속으로 이어지는 수열의 최대 길이 반환
시간 복잡도가 O(n)이어야 함

✍️ 나의 풀이

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
    let map = new Map();
    let res = 0;

    for (let i = 0; i < nums.length; i++) {
        if (map.has(nums[i]))
            continue ;

        let num = nums[i];
        let left = map.get(num - 1) || 0;
        let right = map.get(num + 1) || 0;
        let len = left + right + 1;
        
        map.set(num - left, len);
        map.set(num, len);
        map.set(num + right, len);
        res = res < len ? len : res;
    }

    return res;
};

num을 돌면서 map에 (숫자)-(자신과 이어진 수열의 길이)를 저장
num - 1과 num + 1 사이에 num이 들어가기 때문에
각각의 수열 길이를 더한 것으로 갱신됨
left와 right 사이의 값들은 전부 연결되어 있으므로
굳이 값을 안바꿔도 되고 수열의 양 끝인 left와 right만 길이 수정
(추가로 들어오는 값은 그 둘만 확인하게 됨)
값을 바꿀 때마다 여태까지의 최대 길이도 갱신

📌 결과

Accepted
Runtime 112ms (Beats 60.53%)
Memory 77.12MB (Beats 16.37%)

📚 러닝 포인트

사실 이번 코드는 다른 사람의 코드를 참고해서 작성했다. 단순히 sorting 후 순회하면서 +1인지 아닌지 확인하고 최대 길이를 재면 되는데, sort()의 시간 복잡도가 O(nlogn)이기 때문에 해당 알고리즘은 사용할 수 없었다. 그래서 한참을 머리를 굴려봤는데 도저히 배열을 한 번만 돌면서 체크하는 방법이 생각이 안났다. 솔루션도 꽤 오래 찾아봤는데 다들 sort를 사용하고 있었고... 그러던 중 유일하게 다른 접근법을 사용한 코드를 하나 찾았다. 보자마자 유레카! 외치고 object -> map으로만 바꿔서 구현해봤다. 나도 언젠가는 이렇게 기발한 알고리즘 한 번에 떠올리고 싶다...