Longest Consecutive Sequence

[hsskey]

Longest Consecutive Sequence

정렬되어 잇지 않은 정수형 배열 nums가 주어졌다. nums 원소를 가지고 만들 수 있는 가장 긴 연속된 수의 갯수는 몇개인지 반환하시오.

📝 제약조건

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

💡 예시

• Input: [100, 4, 200, 1, 3, 2]
  • Output: 4 (가장 긴 연속된 수: [1, 2, 3, 4])
• Input: [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
  • Output: `9 (가장 긴 연속된 수: [0, 1, 2, 3, 4, 5, 6, 7, ,8])

문제 해결 과정

Step 1: 문제 이해하기

• input Size: n (n이 커지면 커질수록 실행시간이 증가)
  • n의 범위가 10^5까지이므로 10^7을 넘어서면 안되니까 O(n^2)의 시간복잡도로 문제를 풀게되면 10^10으로 시간초과(❌)
  • O(n) or O(nlogn)
• nums의 길이가 0이 될수 있다 → 빈배열에 대한 처리 예상
• -10^9 <= nums[i] <= 10^9
  • 특정 언어에서는 int형 자료형이 4byte로 되어있다.
  • 4byte의 범위는 -2^31 ~ 2^31 - 1 로 표현을 할수 있는 자료형이다.(2 10^9 ~ 2 10^9 → int 자료형으로 충분히 표현가능한 숫자범위)

Step 2: 접근 방법

• 직관적으로 생각하기 (주어진 문제를 어떻게 풀것인가 생각해본다면?)
  • 눈으로 한번 왼쪽에서 오른쪽으로 훑으면서 연속된 수를 내가 찾아야 되는구나
  • 100을 봤을때 101이 있나? 나머지 모든곳을 한번 살펴 본다.
  • 이번엔 4를 보고나서 연속된 수인 5가 있나? 하면서 배열을 살펴본다
  • 원소의 개수가 n개라면 탐색시 n-1을 탐색
  • worst case: n^3

// (next in nums) * while문 * for문 → O(n^3)  
for i range(n):
  while next in nums: // 해당 조건문은 포인터가 배열의 요소를 가리키며 움직이면서 찾는과정을 의미
    count += 1
    next += 1

• 개선할수 있는부분이 있다면?

  • 일일이 포인터를 통해 찾아보지않고 dictonary를 이용할수있다면 List안에 찾는 숫자가 있는지 하나씩 탐색하지않고(next in nums)
  • dictonary에 있는지 바로 O(1)로 확인가능(next in nums_dict)
  • 1,2,3,4가 나왔으면 **첫번째 시작점이 쭉 연속된 수를 한번 골라내면 그 안에 있는 요소끼리 연속된 수를 찾는 중복된 과정이 불필요!
  • 가장 긴 연속된 수를 찾는게 목적이니까 첫 시작점만 알 수 있다면 중복된 탐색과정을 제거 할 수 있다.
  • if 시작점일때 만 (조건문을 통과할때만 while문을 실행할수 있도록 변경)
  • 1이 나오면 1 앞에 숫자가 있는가?(1 부터 탐색) 2가 나오면 2앞에 숫자가 있는가?(2 탐색과정제외)
  • if prev not in nums_dict
  • n(반복문) + n(탐색되는 내용만 반복문 실행) → O(2n)

• 메모리 사용

  • 정렬 O(nlogn)으로도 풀이 가능 (바로 왼쪽에서 오른쪽으로 훑어 보면서 가장 긴 연속된 수를 구할 수 있다.)
  • 1. O(nlogn)으로 정렬
  • 2. O(n) 반복문의 탐색과정에서 연속된 수를 찾는다.

Step 3: 코드 설계

• 문제의 제약조건과 입력값을 고려하여 효율적인 알고리즘을 설계합니다.

Step 4: 코드 구현

• 설계한 알고리즘에 따라 코드를 작성하고 테스트합니다.

function longestConsecutive(nums) {
    if(nums.length === 0) return 0
    const dict = {}
    let longest = 0
    for(let num of nums) {
        dict[num] = true
    }
    for(let num in dict) {
        let parsedNum = Number(num)
        if(!((parsedNum - 1) in dict)) {
            let cnt = 1
            while(parsedNum + 1 in dict) {
                cnt += 1
                parsedNum++
            }
            longest = Math.max(cnt, longest)
        }
    }
    return longest
}

console.log(longestConsecutive([0, 1, 2, 3, 4, 5, 6, 7, ,8]))

[hsskey]

sort를 이용한 풀이

function longestConsecutive(nums) {
    if(nums.length === 0) return 0
    const setNums = [...new Set(nums)]

    setNums.sort((a, b) => a - b)

    let longest = 0

    for(let i = 0; i < setNums.length; i++) {
        let cnt = 1
        while(true) {
            if(!setNums[i + 1] || setNums[i] + 1 !== setNums[i + 1]) {
                break
            }
            cnt++
            i++
        }
        longest = Math.max(cnt, longest)
    }
    return longest
}