230406 유사 칸토어 비트열

public static int solution(int n, long l, long r) {
    return countOne(n, l, r, 1);
}

public static int countOne(int n, long s, long e, long idx) {
    if (n == 0) {
        return 1;
    }
    int numOnes = 0;
    long subIntervalSize = (long) Math.pow(5, (double) n - 1);
    for (int i = 0; i < 5; i++) {
        if (i == 2 || e < (idx + subIntervalSize * i) || (idx + subIntervalSize * (i + 1) - 1) < s) {
            continue;
        }
        numOnes += countOne(n - 1, s, e, idx + subIntervalSize * i);
    }
    return numOnes;
}

1로 시작한 비트열이 단계마다 1은 11011, 0은 00000으로 확장되는 형태

각 단계는 11011이 확장된 형태이므로 최종 단계 n부터 시작하여 아랫 단계로 내려가면서 동일한 방식으로 셀 수 있음

따라서 n단계에서 부터 인덱스에 해당하는 구간의 1의 갯수를 구하는 메서드를 재귀적으로 호출하여 세어줌

출처:https://school.programmers.co.kr/learn/courses/30/lessons/148652