[148652] 유사 칸토어 비트열

✔ 유사 칸토어 비트열

[프로그래머스 148652]

문제 분석하기

가운데 범위에는 무조건 0이 되기 때문에 범위 안에 있는 값 중에서 가운데 값을 제외하고 1만을 찾도록 함

 

예) 2번째 유사 칸토어 비트열, l = 4, r = 17일 때

2번째 유사 칸토어 비트열은 1번째 유사 칸토어 비트열을 사용하여 만들어지므로 11011 11011 00000 11011 11011

i	i번째 유사 칸토어 비트열
0	1 → 5⁰개를 가짐
1	11011 → 5¹개를 가짐
2	11011 11011 00000 11011 11011 → 5²개를 가짐

i	r (= 17)보다 크거나	l (= 4)보다 작다면	유사 칸토어 비트열
0	1 + 5 * i = 1	1 + 5 * (i + 1) -1 = 5	11011 11011 00000 11011 11011 범위를 벗어나지 않으므로 사용 O
1	1 + 5 * i = 6	1 + 5 * (i + 1) -1 = 10	11011 11011 00000 11011 11011 범위를 벗어나지 않으므로 사용 O
2	1 + 5 * i = 11	1 + 5 * (i + 1) -1 = 15	11011 11011 00000 11011 11011 모두 0이므로 사용 X
3	1 + 5 * i = 16	1 + 5 * (i + 1) -1 = 20	11011 11011 00000 11011 11011 범위를 벗어나지 않으므로 사용 O
4	1 + 5 * i = 21	1 + 5 * (i + 1) -1 = 25	11011 11011 00000 11011 11011 범위를 벗어나지 않으므로 사용 X
다음 각각에 대해 11011을 사용해 같은 방식을 반복 그 다음으로 1을 사용해 같은 방식을 반복

손으로 풀어보기

1. 이전 유사 칸토어 비트열을 사용
2. i가 2일 경우 모두 0으로 되어 있거나 0이므로 제외
3. 각 11011의 첫 번째 위치인 index + 5 * i가 r보다 크다면 범위를 벗어나므로 제외
4. 각 11011의 마지막 위치인 index + 5 * (i + 1) - 1이 l보다 크다면 범위를 벗어나므로 제외
5. 이전 유사 칸토어 비트열이 0이 될 때까지 반복하며 1의 갯수를 구하도록 함

슈도코드 작성하기

n(알고싶은 유사 칸토어 비트열)
l, r(1의 개수가 몇 개인지 알고 싶은 구간)
answer(구간 내의 1의 개수) = 1의 개수 세기 함수
answer 반환

1의 개수 세기 함수(n, l, r, index) {
    if(n이 0이라면)
        1을 반환
    number(1의 갯수)
    part(이전 유사 칸토어 비트열의 길이) = 5의 n - 1의 제곱
    for(i -> 0부터 5만큼) {
        if(i가 2이거나, index + part * i가 r보다 크거나, index + part * (i + 1) -1이 l보다 작다면)
            0이거나 범위를 벗어나므로 continue
        number += 1의 개수 세기 함수(n - 1, s, e, index + part * i)
    }
    number 반환
}

코드 구현하기

/**
 * 148652) 유사_칸토어_비트열
 */
public class L089_148652 {
    // n(알고싶은 유사 칸토어 비트열)
    // l, r(1의 개수가 몇 개인지 알고 싶은 구간)
    public int solution(int n, long l, long r) {
        // answer(구간 내의 1의 개수) = 1의 개수 세기 함수
        int answer = countOne(n, l, r, 1);
        // answer 반환
        return answer;
    }

    // 1의 개수 세기 함수
    private int countOne(int n, long l, long r, long index) {
        // n이 0이라면
        if (n == 0)
            // 1을 반환
            return 1;
        // number(1의 갯수)
        int number = 0;
        // part(이전 유사 칸토어 비트열의 길이) = 5의 n - 1의 제곱
        long part = (long) Math.pow(5, n - 1);
        for (int i = 0; i < 5; i++) {
            // 가 2이거나, index + part * i가 r보다 크거나, index + part * (i + 1) -1이 l보다 작다면
            if (i == 2 || r < index + part * i || index + part * (i + 1) - 1 < l)
                // 0이거나 범위를 벗어나므로 continue
                continue;
            // number += 1의 개수 세기 함수(n - 1, s, e, index + part * i)
            number += countOne(n - 1, l, r, index + part * i);
        }
        // number 반환
        return number;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L089_148652 solution = new L089_148652();

        int n = 2;
        long l = 4;
        long r = 17;

        int result = solution.solution(n, l, r);

        System.out.println(result);
    }
}