[LeetCode] 842. Split Array into Fibonacci Sequence

문제

숫자로만 이루어진 문자열 num을 잘라서 피보나치 같은 수열을 만들 수 있으면 그 수열을, 만들 수 없으면 []를 반환합니다.

조건은 다음과 같습니다.

• 수열의 길이는 3 이상이어야 합니다.
• 모든 i에 대해 f[i] + f[i + 1] === f[i + 2]가 성립해야 합니다.
• 각 수는 0 <= f[i] < 2^31이어야 합니다.
• 앞자리에 0이 붙은 조각("01")은 쓸 수 없습니다. 단, "0" 한 글자는 허용합니다.

입력: "1101111"
출력: [11, 0, 11, 11]

입력: "0123"
출력: []   // "01"은 앞자리 0이라 사용 불가

접근

앞의 두 수만 정하면 나머지는 정해진다

피보나치 수열은 앞의 두 수를 더해 다음 수가 정해집니다. 그래서 실제로 "고르는" 것은 첫 번째 수와 두 번째 수를 어디서 자를지뿐이고, 세 번째 수부터는 맞는지 확인만 하면 됩니다.

이 성질을 백트래킹에 적용하면 다음과 같습니다.

1. 현재 위치 start에서 자를 길이를 1글자, 2글자, ... 순서로 시도합니다.
2. 수열에 수가 2개 이상 있으면, 잘라낸 수가 앞의 두 수의 합과 같은지 넣기 전에 확인합니다.
3. 맞으면 넣고 다음 위치로 넘어가고, 그 길이 끝에서 실패하면 빼고(pop) 다른 길이를 시도합니다.
4. 문자열 끝에 도달했을 때 수열 길이가 3 이상이면 성공입니다.

가지치기

• 합보다 작으면 continue: 더 길게 자르면 수가 커지니 합에 도달할 수 있습니다.
• 합보다 크면 break: 더 길게 자르면 더 커질 뿐이라 볼 필요가 없습니다.
• 2^31 이상이면 break: 같은 이유입니다. 이 조건 때문에 한 조각은 최대 10자리라서 분기 수가 크게 줄어듭니다.
• 앞자리 0이면 break: "0"으로 시작하는 조각은 "0" 한 글자만 가능하고, "02", "023"처럼 길게 잘라도 전부 앞자리 0입니다.

풀이

function splitIntoFibonacci(num: string): number[] {
    const MAX = Math.pow(2, 31);
    const n = num.length;

    const seq = [];

    const backTrack = (start: number) => {
        if (start === n) return seq.length >= 3;
        
        for (let end = start + 1; end <= n; end++) {
            if (num[start] === '0' && end - start > 1) break;
            
            const slice = Number(num.slice(start, end));
            if (slice >= MAX) break;
            
            if (seq.length >= 2) {
                const sum = seq.at(-2) + seq.at(-1)
                if (sum > slice) continue;
                if (sum < slice) break;
            }

            seq.push(slice);
            if (backTrack(end)) return true;
            seq.pop();
        }

        return false;
    }

    return backTrack(0) ? seq : []
};

헷갈렸던 부분

1. 한 글자씩만 자르면 백트래킹이 아니다

처음에는 Number(num[idx])로 한 글자씩 넣으면서 재귀를 한 갈래로만 돌렸습니다. 이렇게 하면 11, 110 같은 여러 자리 수를 시도하지 못하고, 한 번 틀리면 다른 길을 찾지 않고 바로 실패합니다.

백트래킹이 되려면 자를 길이를 for 문으로 여러 개 시도하는 분기가 있어야 합니다.

2. 수를 넣기 전에 검사한다

처음 코드는 새 수를 넣고 나서 다음 호출에서 이전 배열을 검사했습니다. 그러면 문자열 끝에 도달했을 때 마지막으로 넣은 수는 검사 없이 반환됩니다("124" → [1, 2, 4]). 넣기 전에 합과 비교하면 이 문제가 없습니다.

3. 조각 길이는 end - start

if (num[start] === '0' && end - start + 1 > 1) break; // ❌
if (num[start] === '0' && end - start > 1) break;     // ✅

slice(start, end)는 end를 포함하지 않으므로 조각 길이는 end - start입니다. + 1을 붙였더니 "0" 한 글자(길이 1)까지 길이 2로 계산되어 막혔고, "1011" → [1, 0, 1, 1] 케이스에서 틀렸습니다.

+ 1은 [start, end]처럼 양 끝을 모두 포함하는 구간의 길이를 셀 때만 붙입니다.

복잡도

• 시간: 첫 두 수는 각각 최대 10자리라서 조합이 약 100가지이고, 세 번째 수부터는 합이 정해져 있어 사실상 분기 없이 한 번 훑습니다. 따라서 O(n)에 가깝습니다(상수 약 100).
• 공간: 재귀 깊이와 seq 길이 모두 최대 n이므로 O(n)입니다.