DaleStudy | Leetcode Study 1주차 - Longest Consecutive Sequence

Leetcode Study

문제

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. You must write an algorithm that runs in O(n) time.

 

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

 

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

 

Example 3:

Input: nums = [1,0,1,2]
Output: 3

Constraints:

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

 

풀이

 

이 문제는 배열에 연속된 숫자가 몇 번이나 반복되는지 확인하는 문제인데, 여기서 생각해야할 부분은 연속된 숫자의 모음이 한 번만 존재하는 것이 아니라 여러번 존재할 수 있기 때문에 Math.max를 사용해서 비교해야한다는 점이다. 그리고 문제에서는 unsorted라고 작성되어 있기 때문에 이 부분은 "정렬을 한 뒤에 구현해라" 라고 힌트를 주는 것이다.  

 

예시 3번을 보면 1에서 1으로 가는 부분은 연속된 숫자의 모음으로 정의하지는 않지만, 그래도 연속되었다고 정의하는 것으로 볼 수 있다. 즉, 3가지로 경우의 수를 나눠볼 수 있다. 

	연속의 유무	숫자 증가
같은 수	연속 O	증가 X
연속된 수	연속 O	증가 O
그 외	연속 X	증가 X

function longestConsecutive(nums: number[]): number {
    if (!nums.length) return 0;

    nums.sort((a, b) => a - b);
    let longest = 1;
    let currentStreak = 1;

    for (let i = 1; i < nums.length; i++) {
        if (nums[i] === nums[i - 1]) continue;
        if (nums[i] === nums[i - 1] + 1) {
            currentStreak++;
        } else {
            longest = Math.max(longest, currentStreak);
            currentStreak = 1;
        }
    }


    return Math.max(longest, currentStreak);
};

 

currentStreak가 0부터 시작하는 것이 아니라 1부터 시작하는 이유는, 현재의 원소 포함해야하기 때문에 1부터 시작하는 것이다. 0부터 시작하게 되면 항상 1이 부족하게 만들어지게 된다. 

 

 

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