[Leetcode] 128. Longest Consecutive Sequence - JS

https://leetcode.com/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
- 정렬되지 않은 정수 배열 nums가 주어질 때, 가장 긴 연속 요소 시퀀스의 길이를 반환하라.
- 반드시 O(n)의 시간 복잡도로 해결해야한다.

제한조건
--------------------
- 0 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9

 

2. 접근 방법

접근방법
--------------------
sort() 메서드는 시간복잡도가 O(n log n)이므로 사용할 수 없다.
중복된 요소가 있을 수 있으니 Set()으로 유일한 요소만 남겨둔다.

nums = [100,4,200,1,3,2]
setNums = [1,2,3,4,...100,...200]

setNums에서 연속된 요소의 가장 긴 길이가 4인것을 어떻게 알 수 있는가?
바로 1부터 시작해서 연속된 숫자가 4개가 가장 많기 때문이다.
그럼, 1부터 시작하는 것은 어떻게 알 수 있는가?

만약, 1보다 작은 숫자인 0이 있었다면...
시작점이 0이 되었을 것이다.
즉, n - 1이 존재하는 지 확인하고 존재하지 않으면 n이 시작점이라고 가정하여 접근하는 것이다.

n이 시작점이라고 가정을 했다면 n 부터 시작하는 길이(length)를 1로 초기화하고
n에서부터 연속되는 숫자가 setNums에 존재하는지 확인하여 길이를 갱신한다.

마지막으로 이전 longest 값과 비교하여 length 중 큰 값으로 갱신한다.

 

 

3. 코드

var longestConsecutive = function(nums) {
    if (nums.length === 0) return 0;

    const numSet = new Set(nums);
    let longest = 0;

    for (let num of numSet) {
        if (!numSet.has(num - 1)) {
            let length = 1;

            while (numSet.has(num + length)) {
                length++;
            }

            longest = Math.max(longest, length)
        }
    }
    return longest;
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(n)

 

해쉬맵을 사용하면 될 것 같은데, 시간 복잡도를 O(n)으로 풀어야한다는 조건이 있다보니 좀처럼 방법이 떠오르지 않았다.

결국 다른 사람의 풀이를 보고 공부했다.

 

시작점을 선정하는 방법을 n - 1 값의 존재 유무로 판단하는 방법이 기발한 것 같다.

다른 비슷한 유형의 문제에서 적용해보면 좋을 것 같다.