[LeetCode] Longest Consecutive Sequence

문제링크

Longest Consecutive Sequence - LeetCode

 

주어진 숫자 배열 nums에서 가장 길게 연속적으로 연결된 수의 길이를 구하는 문제
([1,2,3,4,5,7,8,9] => output = 5 (1,2,3,4,5))

조건 : 시간복잡도는 무조건 O(n)이하로 작성해야한다.
주의사항 : [1,2,2,2,3,3,4] 같은 배열은 output이 2가 아니라 4이다.

접근 방법

조건에 맞춰 주어진 배열을 단 한번만 순회하도록 작성하였다. (O(2n) === O(n))

1. 주어진 배열을 정렬하고 (O(n)), Set을 사용하여 주의사항의 경우를 배제한다.

2. nums.length가 1인 경우 1을 return 한다.

3.1 nums[i-1] + 1 === nums[i] 인 경우 sequenceNum += 1
3.2 nums[i-1] + 1 !== nums[i] 인 경우 sequenceNum = 1
각 경우를 처리하고 output을 sequenceNum의 최대값으로 업데이트 해준다.


 

 

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
    let output = 0;
    let sequenceNum = 1;
    
    nums = [...new Set(nums.sort((a,b) => a - b))];
    
    if(nums.length === 1) return 1;
    
    for(let i = 1; i < nums.length; i++){
        if(nums[i-1] + 1 === nums[i]) sequenceNum++;
        else sequenceNum = 1;
        
        output = Math.max(output, sequenceNum);
    }
    
    return output;
    
};