유사 칸토어 비트열 (연습문제)

원본 : https://school.programmers.co.kr/learn/courses/30/lessons/148652

프로그래머스

 

풀이

class Solution {
    public int solution(int n, long l, long r) {
        l--;
        String str = "1";
        double pow = Math.pow(5, n);

        while (n-- > 0) {
            StringBuilder sb = new StringBuilder();
            long start = (long) Math.floor(l / pow);
            long end = (long) Math.ceil(r / pow);
            long idx = 0;

            for (char ch : str.toCharArray()) {
                if (idx >= end) {
                    break;
                }

                if (start <= idx) {
                    if (ch == '0') {
                        sb.append("00000");
                    } else {
                        sb.append("11011");
                    }
                } else {
                    l -= pow;
                    r -= pow;
                }

                idx++;
            }

            pow /= 5;
            str = sb.toString();
        }

        long idx = 0;
        int cnt = 0;

        for (char ch : str.toCharArray()) {
            if (idx >= r) {
                break;
            }

            if (l <= idx) {
                if (ch == '1') {
                    cnt++;
                }
            }

            idx++;
        }

        return cnt;
    }
}