이번 글에서는 정수 배열을 인자로 받아, 배열 안에 존재하는 가장 긴 연속 숫자 시퀀스의 길이를 찾아 반환하는 JavaScript 함수를 작성해 보겠습니다. 여기서 말하는 연속 시퀀스란 값이 1씩 증가하는 숫자들의 집합을 의미하며, 배열 내에서 서로 붙어 있지 않아도 괜찮습니다(비연속적 위치 허용).
문제 예시
입력 배열이 다음과 같다고 가정해 보겠습니다.
const arr = [4, 6, 9, 1, 2, 8, 5, 3, -1];
이 배열에는 1, 2, 3, 4, 5, 6으로 이어지는 시퀀스가 있으며, 이것이 가장 긴 연속 증가 시퀀스입니다. 따라서 함수의 반환값은 6이 되어야 합니다.
접근 방법
가장 효율적인 해결 방법은 배열의 모든 숫자를 Set 자료구조에 저장한 뒤, 각 숫자가 시퀀스의 시작점인지 확인하는 것입니다. 어떤 숫자보다 1 작은 값이 Set에 없다면 그 숫자는 새로운 시퀀스의 출발점입니다. 시작점을 발견하면 1씩 증가하는 숫자가 존재하는 동안 길이를 늘려 나가고, 그 과정에서 얻은 길이 중 최댓값을 기록합니다.
이 방식은 각 숫자를 최대 두 번만 방문하므로 전체 시간 복잡도가 O(n)으로 매우 효율적입니다.
구현 코드
const arr = [4, 6, 9, 1, 2, 8, 5, 3, -1];
const consecutiveSequence = (arr = []) => {
const numSet = new Set(arr);
let max = 0;
for (let num of numSet) {
// num - 1이 없다면 num은 시퀀스의 시작점
if (!numSet.has(num - 1)) {
let curr = num;
let length = 1;
while (numSet.has(curr + 1)) {
curr += 1;
length += 1;
}
max = Math.max(max, length);
}
}
return max;
};
console.log(consecutiveSequence(arr));
실행 결과
6
동작 원리 상세 분석
코드는 다음 단계로 동작합니다.
- Set 생성: 배열의 모든 요소를
Set에 저장해 중복을 제거하고, O(1) 시간에 특정 숫자의 존재 여부를 확인할 수 있게 만듭니다. - 시작점 판별: 각 숫자에 대해
num - 1이 Set에 없는 경우에만 검사를 시작합니다. 이미 앞 숫자가 있다면 해당 숫자는 더 긴 시퀀스의 중간 부분이므로 건너뛰어 불필요한 반복을 줄입니다. - 시퀀스 확장: 시작점부터
curr + 1이 존재하는 동안 반복하며 시퀀스의 길이를 셉니다. - 최댓값 갱신: 계산된 길이와 현재 최댓값을 비교해 더 큰 값을 저장하고, 마지막에 반환합니다.
위 예시 배열에는 (-1), (1, 2, 3, 4, 5, 6), (8, 9)라는 세 개의 독립된 시퀀스가 존재합니다. 각각의 길이는 1, 6, 2이므로 최종 결과는 가장 긴 6이 출력됩니다.
마무리
단순 정렬 후 순회하는 방법(O(n log n))도 가능하지만, Set을 활용하면 정렬 없이 선형 시간에 문제를 해결할 수 있습니다. 특히 데이터 크기가 클 때 이 접근 방식이 성능 면에서 큰 이점을 제공합니다.