Leetcode 128. Longest Consecutive Sequence

릿코드 128번문제 Longest Consecutive Sequence

자바스크립트로 Leetcode 128 번문제인 Longest ... 를 풀어보겠습니다. 난이도 - 중

---

문제설명

 

 

Medium

 

 

 

Companies

 

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

 

Constraints:

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

인자로 받은 integer 배열 안에서 연속적으로 나오는 숫자의 최대값을 구하는 문제 입니다.

 

예제에서 보이는 것처럼 예제 1은 1, 2, 3, 4 가 모두 배열에 포함되어 있기 때문에 4를 리턴합니다.

 

예제2는 0에서 8까지 연속적으로 모두 숫자가 들어있기 때문에 9를 리턴합니다.

 

이 문제의 핵심은 시간복잡도를 O(n) 으로 풀어야 한다는 것입니다.

---

문제풀이

자바스크립트의 Set 을 사용해서 접근 해 보았습니다.

 

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
    let maxScore = 0;
    const numSet = new Set(nums);
    for (const num of numSet) {
        const prevNum = num - 1;
        if (numSet.has(prevNum)) continue;
        let [ currNum, score ] = [ num, 1 ];
        while (numSet.has(currNum + 1)) {
            currNum++;
            score++;
        }
        maxScore = Math.max(maxScore, score);
    }
    return maxScore;
};

1번 예제를 같이 보며 생각해 보겠습니다.

Input: nums = [100,4,200,1,3,2]

 

리턴할 값을 maxScore 로 두고, set의 숫자들을 돌며 연속적으로 등장하는 interger 가 얼마나 있는지를 score 변수에 저장해가며 문제를 풀었습니다. set 이 순차대로 돈다는 가정하에 (순차적으로 돌지 않더라도 결과는 같습니다) 아래에 차례대로 for loop 안에서의 변화에 대해 관찰해 보겠습니다.

 

일단 배열의 첫번째 값인 100이 num 에 들어옵니다.

99가 prevNum에 할당되고 99는 numSet 에 포함이 되어 있지 않으므로 currNum에 100, score에 1 값이 할당됩니다.

넘셋이 currNum+1 인 101을 가지고 있지 않으므로 while함수는 false가 되고 maxScore는 현재 maxScore(0)과 score(1) 둘중 최대값인 1로 할당이 됩니다.

---

다음 값인 4가 num 에 들어옵니다.

3이 prevNum에 할당되고 3이 numSet에 포함이 되어 있으므로 continue를 만나 다음 루프를 돕니다.

---

다음 값 200이 num에 할당되고, 199는 numSet 에 없으므로 currNum에 200, score에 1 값이 할당됩니다.

currNum+1인 201이 넘셋에 없으므로 while함수가 false가 되고 maxScore는 현재 maxScore(1)과 score(1) 둘중 최대값인 1로 할당이 됩니다.

---

다음값 1이 num에 할당되고, 0은 numSet에 없으므로 currNum에 1, score에 1이 할당됩니다.

currNum+1인 2가 넘셋에 존재하므로 while함수가 true가 되고 while 함수가 계속 실행이 되는동안 currNum값이 1씩 증가, score값 역시 1씩 증가하게 됩니다. 여기서 핵심은 자바스크립트의 Set의 has 함수는 시간복잡도가 O(1)이기 때문에 for loop 안에 있어도 전체적인 시간복잡도가 O(n)이 된다는 것입니다.

 

currNum이 증가하더라도 다음 값인 3, 4가 존재하게 되므로 while 루프가 다 돈 후 score 값에는 4가 할당되어 있습니다. maxScore(1)과 score(4) 둘중 최대값인 4가 maxScore 값에 할당이 됩니다.

 

 

여기까지 생각 후 어떤 원리로 동작하는지 살펴보겠습니다.

 

단순하게 보면, 배열의 각 값을 순차적으로 순회하면서 해당 값보다 1 작은 값은 무시하고(작은 값은 1 큰값을 while루프를 돌때에 계산이 이미 되어있거나 되기 때문) 1 큰 값이 존재할 경우에 계속 score 값을 증가 시키는 것이 알고리즘의 핵심이라 할 수 있습니다.

 

예제 1의 경우 배열 안 값 중 1을 만나게 될 경우 4까지 while loop 가 돌며 score 에 4 값이 저장이 되고 이것이 결과값이 되는 것입니다.

 

---

그럼 예제 2는 어떨까요?

 

예제 2는 0을 만나게 되었을 경우, 똑같이 maxScore값이 9가 될 것입니다.

 

다른 예제를 한번 들어보겠습니다.

 

Input: nums = [9,8,200,1,99,3,2,100,102,101]

위와 같은 경우, 순서대로 보자면 8를 돌때 maxScore 값이 2가 되고(8, 9),

99를 돌때 maxScore 값이 4가 되고(99, 100, 101, 102),

2를 돌때 maxScore 값이 4가 되어(score가 2 이므로 변화가 없습니다) 최종적으로 5를 리턴하게 됩니다.

 

결과

문제를 잘 푼 것을 확인 할 수 있습니다.

 

이번 128번 문제 Longest Consecutive Sequence 같은 경우, Set 함수의 시간복잡도가 O(1)인것을 이용하는 것이 문제풀이의 핵심이라는 생각이 드네요. 자바스크립트로 풀었지만 자바로 풀 경우도 Set<Integer> set = new HashSet<>(); 을 이용해 set 에 값을 add 한 후 같은방법으로 접근하면 풀 수 있습니다.

 

이상 포스팅을 마치겠습니다.

 

※ 앞으로 모든 문제를 JavaScript 로 올릴 예정입니다.

 

다른 문제 풀이도 깃헙에서 확인 할 수 있습니다.