[Programmers] Lv2 유사 칸토어 비트열

유사 칸토어 비트열

문제 요약

유사 칸토어 비트열 K는 이전 순서의 유사 칸토어 비트열의 1을 11011로 치환하고 0을 00000으로 치환시켜 확장시킨 것을 말한다. K0 = 1 K1 = 11011 K2 = 11011 11011 00000 11011 11011 ...

n번째 유사 칸토어 비트열에서 l번째부터 r번째 까지 1이 나온 횟수를 반환하라는 문제이다.

최초 접근

n = 20 이고 길이 자체가 5^n 까지 확장이 되기 때문에 단순히 문자열을 대치하는 방식으로는 시간 복잡도 측면이나 공간 복잡도 측면에서도 효율적이지 않아 재귀함수에 백트래킹을 적용하는 방식을 선택하였다.

import java.util.*;
class Solution {
    
    private int answer = 0;
    
    private long l = 0L;
    
    private long r = 0L;
    
    private int maxDepth = 0;
    
    private boolean isOutofRange(long from, long to) {
        if( to < this.l) {
            return true;
        } else if( from > this.r ) {
            return true;
        }
        
        return false;
    }
    
    private void split(int depth, long from, long to, boolean p) {
        if(isOutofRange(from, to)) return; 
        
        if(depth == 0) {
            //System.out.println("from : " + from + " to : " + to + " p : " + p);
            if(from >= this.l && from <= this.r) {
                if(p) {
                    answer++;
                }
            }
            return ;
        }
        
        long stride = (to-from)/5;
        if(stride == 0) return;
        
        if(p == true) {
            split(depth - 1, from + stride*0, from + stride*1, true);
            split(depth - 1, from + stride*1, from + stride*2, true);
            split(depth - 1, from + stride*2, from + stride*3, false);
            split(depth - 1, from + stride*3, from + stride*4, true);
            split(depth - 1, from + stride*4, from + stride*5, true);
        }else {
            split(depth - 1, from + stride*0, from + stride*1, false);
            split(depth - 1, from + stride*1, from + stride*2, false);
            split(depth - 1, from + stride*2, from + stride*3, false);
            split(depth - 1, from + stride*3, from + stride*4, false);
            split(depth - 1, from + stride*4, from + stride*5, false);
        }
    }
    
    public int solution(int n, long l, long r) {
        this.l = l-1;
        this.r = r-1;
        long limit = (long)Math.pow(5, n);
        long stride = limit / 5;
        //System.out.println("stride : " + stride);
        split(n-1, 0, stride, true);
        split(n-1, stride, stride*2, true);
        split(n-1, stride*2, stride*3, false);
        split(n-1, stride*3, stride*4, true);
        split(n-1, stride*4, stride*5, true);
        
        return answer;
    }
}

imageURL

위 코드를 이용하여 통과는 했지만 이 문제가 프랙탈 구조를 이용하여 해결이 가능할 것 같다는 생각이 들어 조금 더 생각을 해보다가 다른 접근을 하게 되었다.

다른 접근

이 문제는 일종의 프랙탈 구조를 가지고 있다는 점에 착안을 하였다. P0 = 1 P1 = 11011 Z0 = 0 이라고 하고, Zn = Zn-1 Zn-1 Zn-1 Zn-1 Zn-1 이라고 하자 Pn = Pn-1 Pn-1 Zn-1 Pn-1 Pn-1 이 성립한다.

Pn 상의 한 점 i 에 대하여 생각을 해보자 ( l-1 <= i < r) i가 Pn을 구성하는 Pn-1, Zn-1 로 구성된 블록들 중 세번째 블록에 속한다면 해당 좌표는 무조건 0이다. Zn 에 속하지 않는 좌표라도 세번 째에 속한다면 무조건 0이다. 기본 구성이 되는 P1의 세번째는 무조건 0이기 때문이다.

따라서 주어진 좌표를 5로 계속 나누어가며 해당 좌표가 0이 되는 조건에 해당하는지 체크하면 쉽게 1과 0을 판별할 수 있다.

이를 기반으로 아래와 같은 의사 코드를 작성할 수 있다.

def search(n : int) -> int :
    if n % 5 == 2 return 0
    if n < 5 : return 1
    
    return dfs(n / 5)

이제 이 조건을 아래와 같이 풀이로 옮기면 해결이 된다.

class Solution {
    
    int dfs(long n) {
        if(n % 5 == 2) return 0;
        if(n < 5) return 1;
            
        return dfs(n/5);
    }
    
    public int solution(int n, long l, long r) {
        int answer = 0;
        
        for(l--; l < r ; l++) {
            answer += dfs(l);
        }
        
        return answer;
    }
}

imageURL