문제 정의
다음과 같은 규칙으로 정의되는 증가 수열을 생각해 봅시다.
- 수열의 첫 번째 항은 seq(0) = 1입니다.
- 수열에 포함된 각 x에 대해 y = 2 * x + 1과 z = 3 * x + 1 역시 반드시 수열에 포함되어야 합니다.
- 위 규칙으로 만들어지지 않는 다른 숫자는 수열에 존재할 수 없습니다.
따라서 이 수열의 처음 몇 개 항은 다음과 같습니다.
[1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...]
즉, 우리가 작성해야 할 함수는 숫자 n을 입력받아 이 수열의 n번째 항을 반환하는 것입니다.
접근 방법
이 문제는 두 개의 포인터(인덱스)를 활용하면 매우 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 포인터 x는 '2 * seq[x] + 1' 후보를, 포인터 y는 '3 * seq[y] + 1' 후보를 각각 추적합니다.
- 매 단계마다 두 후보 값 중 더 작은 값을 수열에 추가하고, 해당 후보를 만든 포인터를 앞으로 이동시킵니다.
- 두 후보 값이 같다면 중복을 피하기 위해 두 포인터를 모두 이동시킵니다.
이 방식은 마치 두 개의 정렬된 스트림을 병합하는 것과 유사하며, 각 항을 한 번씩만 처리하므로 시간 복잡도는 O(n)입니다.
예제 코드
const num = 10;
const findNth = n => {
let seq = [1], x = 0, y = 0
for (let i = 0; i < n; i++) {
let nextX = 2 * seq[x] + 1, nextY = 3 * seq[y] + 1
if (nextX <= nextY) {
seq.push(nextX)
x++
if (nextX == nextY)
y++
} else {
seq.push(nextY)
y++
}
}
return seq[n];
}
console.log(findNth(num));실행 결과
22
num이 10일 때 함수는 수열의 10번째 항인 22를 반환합니다. 코드에서 nextX와 nextY를 비교해 더 작은 값을 수열에 삽입하고, 값이 같을 경우 두 포인터를 함께 증가시켜 중복 요소가 수열에 들어가지 않도록 처리하는 점이 핵심입니다.