프로그래머스 Lv2 유사 칸토어 비트열 문제

• 프랙탈 구조
  • 작은 부분이 전체와 비슷한 모양이 끊임없이 반복되는 자기 유사성(Self-similarity)을 가진 복잡한 기하학적 형태
• 칸토어 집합
  • 실수에서 0과 1로 이루어진 집합을 3등분해나가면서 가운데 것을 제거하는 작업을 반복하여 얻는 집합
• 프로그래머스 Lv2 유사 칸토어 비트열 문제
  • 해당 문제의 난이도 상승 원인
    • 프랙탈 구조와 칸토어 집합이란 것에 대한 의미를 모르는 상태로 문제 해결 시작
    • 이 중, 프랙탈 구조의 성질인 현재 구조는 이전 구조'들'로 이루어진 것이라는 성질을 전혀 사용하지 못함
    • 또힌 프랙탈 구조와 더불어 칸토어 비트열에서 가운데 구간만 제거하고 이전 구조에 있는 0을 제거하지 못해 카운팅에서 오류 발생
  • 해당 문제를 해결한 방법
    • 프랙탈 구조, 칸토어 집합에 대해 검색을 통해 기초적인 정보를 얻어 사용
    • 현재 구조는 이전 구조'들'로 이루어졌다는 것을 이용해 재귀함수를 통해 해결
  • 처음 방식에서 변경한 방식
    • 처음
      • 처음과 끝이 포함된 지수를 구하여 전체 1의 개수를 구하고 서로 -하여 구한 개수에서 추가로 시작 수의 나머지를 +, 끝의 나머지를 - 하여 답을 구하려함
    • 변경
      • 재귀함수를 이용해 현재 상태에 대한 구조를 구하고 구조를 3등분하여 가운데를 제외한 1의 개수를 구하는 진행 처음 n에서 -1하며 반복
  • 문제의 핵심
    • 프랙탈 구조와 칸토어 집합에 대한 이해가 필요
    • 재귀함수를 사용하는 방법을 알아야함
  • 이 문제의 목적
    • 주어진 것에 대한 핵심 의미를 갖추며 이와 연관된 해결 방법을 사용하기

package PseudoCantorArray;

class PseudoCantorArray {
    public int solution(int n, long l, long r) {
        // 11011 11011 00000 11011 11011
        // 11011
        // 1
        //-----------------------------------
        // 1
        // 11011
        // 11011 11011 00000 11011 11011
        return (int) (recursive(n, r) - recursive(n, l-1));
    }

    public long recursive(int n, long a){
        if(a == 0) return 0;
        if(n == 0) return 1;

        long prevL = (long) Math.pow(5, n - 1);
        long prevCnt = (long) Math.pow(4, n - 1);

        int currSection = (int) ((a - 1) / prevL);
        long remain = (a - 1) % prevL + 1;

        if(currSection < 2){
            return (prevCnt * currSection) + recursive(n - 1, remain);
        }
        else if(currSection == 2){
            return 2 * prevCnt;
        }
        else{
            return (prevCnt * (currSection -1)) + recursive(n - 1, remain);
        }

    }

    public static void main(String[] args) {
        int n = 2;
        int l = 4;
        int r = 17;

        PseudoCantorArray pc = new PseudoCantorArray();

        System.out.println("결과 : " + pc.solution(n, l, r));
    }
}