128. Longest Consecutive Sequence

LeetCode 128번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

Longest Consecutive Sequence - LeetCode

풀이

아이디어

O(n)이기 때문에 정렬 방식은 불가능하다고 판단함. ⇒ 특별한 방법이 생각이 안나서 일일이 구간을 확인해 주는 방식을 시도했다. 배열을 순회할 때 빠르게 원소를 찾아야 하기 때문에 Set을 이용하기로 함.

코드

function longestConsecutive(nums: number[]): number {
  const numSet = new Set<number>(nums);
  let longest = 0;

  for (const startNum of numSet) {
    // 증가하는 구간의 시작점인 경우에만 검사한다. (같은 구간을 중복해서 탐색하는 것을 막기)
    // nums.length가 10000인 경우에 뜬 Time Limit Exceeded를 해결하기 위해 추가함...
    if (numSet.has(startNum - 1)) {
      continue;
    }
    let length = 1;
    let currNum = startNum + 1;
    while (numSet.has(currNum)) {
      length++;
      currNum++;
    }
    longest = Math.max(longest, length);
  }

  return longest;
}

시간 / 공간 복잡도

• 시간 복잡도: for loop 내부에 while loop가 있긴 하지만 증가하는 구간의 시작점일 때만 실행되기 때문에 각 원소에 접근하는 횟수는 결국 1번뿐. O(n)
• 공간 복잡도: Set을 만들기 위해 n만큼의 공간이 필요하므로 O(n)