문제 이해하기
정렬되지 않는 정수 배열 nums가 주어졌을 때, 가장 긴 연속된 수열의 길이를 반환해야 한다.
수열이란?
수열은 일정한 규칙에 다라 수들이 순서대로 나열되어 있는 것을 말한다. 여기서 연속된 수열이란, 수들이 1씩 증가하는 순서로 나열되어 있는 것을 의미한다.
n, n + 1, n + 2, ..., n + k존재 여부를 검사하기
배열 안에서 연속된 수열을 찾기 위해서 어떤 n에 대하여 n + 1, n + 2, …, n + k가 존재하는지 검사해야 한다.
예를 들어 지금 보고 있는 값이 5라면, 6, 7, 8, …이 존재하는지 검사해야 한다. 만약 8까지 존재하고 9가 존재하지 않는다면, 5부터 8까지의 연속된 수열이 존재하는 것이다.
그런데 매번 존재 여부를 검사하기 위해 배열을 순회하면 O(n^2) 비용이 발생한다. 문제의 조건이 O(n) 시간 복잡도를 요구하기 때문에, 배열을 순회하면서 존재 여부를 검사하는 방법은 적합하지 않다. 중복 검사를 제거하기 위해서 Hash Set을 사용하면 O(1) 시간 복잡도로 존재 여부를 검사할 수 있다.
문제 재정의 하기.
연속된 수열을 찾기 위해서 모든 숫자를 찾을 필요가 없다. 5를 검사하면서 이미 6, 7, 8을 찾았다면, 6을 다시 검사할 필요가 없다. 연속된 수열의 시작점만 찾으면 된다. 따라서 이 문제는 다음과 같이 재정의할 수 있다.
=> 가장 긴 연속 수열을 직접 찾는 것이 아니라, 먼저 각 연속 수열의 시작점을 찾는다.
원래 관점: 가장 긴 연속 수열을 어떻게 찾지?
바뀐 관점: 연속 수열의 시작점은 어디지?문제 풀이
자연어로 먼저 설명하기
어떤 입력에 연속 수열의 시작점이 1과 100이라고 가정해보자.
Set의 내용은 다음과 같다.
{1, 2, 3, 4, 100, 101, 102}
시작점은 1과 100이다.
1 - 1 = 0은 Set에 없다. 따라서 1은 시작점이다.
100 - 1 = 99는 Set에 없다. 따라서 100은 시작점이다.
각 시작점에서 다음 숫자가 존재하는 동안 수열을 확장한다.
시작점 1 1 존재 2 존재 3 존재 4 존재 5 없음
수열은 다음과 같다.
1 → 2 → 3 → 4
길이는 4이다.
시작점 100 100 존재 101 존재 102 존재 103 없음
수열은 다음과 같다.
100 → 101 → 102
길이는 3이다.
두 수열의 길이를 비교한다.
max(4, 3) = 4
따라서 최종 정답은 4이다.
전체 전략은 다음과 같이 연결된다.
수열의 시작점을 찾는다. ↓ 각 시작점에서 다음 숫자를 확인한다. ↓ 숫자가 존재하는 동안 길이를 증가시킨다. ↓ 각 수열의 길이를 최댓값과 비교한다. ↓ 가장 긴 길이를 반환한다.
위 내용을 순서대로 정의하면,
배열의 모든 숫자를 Hash Set에 저장한다.
Set에 들어 있는 각 숫자를 순회한다.
현재 숫자의 이전 숫자인 num - 1이 Set에 존재하는지 확인한다.
num - 1이 없다면 현재 숫자는 연속 수열의 시작점이다.
시작점부터 현재 숫자를 1씩 증가시키며 다음 숫자가 Set에 존재하는지 확인한다.
다음 숫자가 존재하는 동안 현재 수열의 길이를 증가시킨다.
하나의 수열 탐색이 끝나면 현재 길이와 최대 길이를 비교한다.
모든 시작점 탐색이 끝나면 최대 길이를 반환한다.코드로 옮기기
function longestConsecutive(nums: number[]): number {
const numSet = new Set(nums);
let maxLength = 0;
for (const n of numSet) {
if (!numSet.has(n - 1)) {
// n is the start of a sequence
let currentNum = n;
let currentLength = 1;
// 다음 숫자가 존재하는 동안 수열을 확장한다.
while (numSet.has(currentNum + 1)) {
currentNum += 1;
currentLength += 1;
}
maxLength = Math.max(maxLength, currentLength);
}
}
return maxLength;
}