Longest Consecutive Sequence

내 풀이

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    longestConsecutive(nums) {
        let sortedNums=nums.sort((a,b)=>a-b);
        let prevNum=sortedNums[0];
        let max=1;
        let count=1;
        if (nums.length===0){
            return 0
        }
        for (let i=1;i<sortedNums.length;i++){
            // 이어진다면
            if (sortedNums[i]===prevNum){
                continue;
            }else if (sortedNums[i]===prevNum+1){
                count+=1;
                prevNum=sortedNums[i];
            // 안 이어진다면
            }else{
                if (count>max){
                    max=count;
                }
                count=1;
                prevNum=sortedNums[i];
            }
        }
        if (max<count){
            max=count;
        }
        return max;

    }
}

같은 숫자가 있어도 consecutive할 수 있음을 모르고 풀어서 if문이...

다른 풀이: Hash Set

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    longestConsecutive(nums) {
        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;
    }
}

세상 깔끔한 코드다. set으로 중복 제거한 후 각 원소에서 시작하는 경우의 가장 긴 consecutive한 배열 길이를 갱신하는 것. if (!numSet.has(num-1)){ 이 코드로 자칫 비효율적인 코드가 될 뻔한 것도 막아주었다.

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    longestConsecutive(nums) {
        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+=1;
                }
                longest=Math.max(longest, length);
            }
        }
        return longest;
    }
}

다른 풀이: Hash Map

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    longestConsecutive(nums) {
        const mp = new Map();
        let res = 0;

        for (let num of nums) {
          // 중복 방지용
            if (!mp.has(num)) {
                // mp.get(num - 1) || 0) --> 왼쪽 수열 길이
                // mp.get(num + 1) || 0) --> 오른쪽 수열 길이
              
              	// 현재 num을 기준으로 새로운 연속 수열 길이를 계산하여
                // 현재 숫자에 저장.
                mp.set(
                    num,
                    (mp.get(num - 1) || 0) + (mp.get(num + 1) || 0) + 1,
                );
              	// 수열의 시작점에 길이 업데이트
                mp.set(num - (mp.get(num - 1) || 0), mp.get(num));
                // 수열의 끝점에 길이 업데이트
                mp.set(num + (mp.get(num + 1) || 0), mp.get(num));
              	// 최대 길이 갱신
                res = Math.max(res, mp.get(num));
            }
        }
        return res;
    }
}

어렵다.
핵심 아이디어: 연속된 수열의 '양 끝 값'에 수열의 길이만 기록하는 것
자세한 건 주석