> [!date] published: 2025-04-04
## 문제
[Longest Consecutive Sequence - LeetCode](https://leetcode.com/problems/longest-consecutive-sequence/description/)
nums 에서 가장 긴 **연속으로 증가하는 부분 배열**의 길이 구하기
## 풀이
### 아이디어
O(n)이기 때문에 **정렬 방식은 불가능**하다고 판단함. ⇒ 특별한 방법이 생각이 안나서 일일이 구간을 확인해 주는 방식을 시도했다. 배열을 순회할 때 빠르게 원소를 찾아야 하기 때문에 Set을 이용하기로 함.
### 코드
```typescript
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)** 이 된다.