[Algorithm] Programmers :: 유사 칸토어 비트열

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

프로그래머스

int counts[5] = { 1,2,2,3,4 };
 
long long GetOneCount(int n, long long index)
{
    if (index < 0) return 0;
    if (n == 1)
    {
        return counts[index];
    }
 
    long long answer = 0;
    long long a = index / pow(5, n - 1);
    long long b = index % (long long)pow(5, n - 1);
 
    for (int i = 0; i < a; ++i)
    {
        if (i == 2) continue;    
        answer += pow(4, n - 1);
    }
 
    if (a != 2) answer += GetOneCount(n - 1, b);
    
    return answer;
}
 
int solution(int n, long long l, long long r) 
{
    return GetOneCount(n, r - 1) - GetOneCount(n, l - 2);
}

일정한 규칙을 가지고 비트열이 생성 됐을 때, 특정구간의 1의 갯수를 구하는 문제이다.

나같은 경우 l에서 r까지의 1의 갯수를 구하기 위해 처음부터 r까지의 1의갯수에서 처음부터 l까지의 1의 갯수를 빼는 방법을 생각해봤다.

l부터 r까지의 1의 갯수 = 처음부터 r까지의 1의 갯수 - 처음부터 l까지의 1의 갯수.

 

그렇다면 n값과 특정 인덱스가 주어졌을 경우, 처음부터 특정인덱스까지의 1의 갯수를 구하는 코드를 작성하면된다.

코드형태는 분할정복을 띄고 있다.

 

현재 n일때의 비트열의 크기는 5^n승으로, n-1로 나누면 각 5개구간의 시작 index를 알 수 있으며, n-1로 나눈 나머지로 해당 구간의 몇번째에 위치하는지 알 수 있다.

 

그리고 특별한 규칙이 이 문제에 존재하는데, n일때의 1의 전체개수는 4 ^ n개라는 것이다.

ex) n == 1 -> 11011  -> 1의개수 4개

      n == 2 -> 11011 11011 00000 11011 11011 11011 -> 1의개수 16개

 

즉, 5구간으로 나눴을 때 현재구간 이전의 구간들에 대해선 1의개수를 바로 구할 수 있다. 

예를들어 현재구간이 세번째일 경우, 이 구간은 반드시 0으로만 이뤄진 구간이고 이 구간의 이전구간인 첫번째와 두번째구간에서의 1의 개수는 각각 4 ^ n-1개가 된다.

그러니 첫번째와 두번째구간에 대해선 바로 합산해주면 된다.

 

그리고 자기 구간에 대해서는 다시 분할한다. 해당구간, 즉 f(n-1)의 전체구간에서 몇번째 index에 해당하는지 알고있기 때문에 분할하는게 가능하다.

 

주의해야할 것은 세번째구간은 항상 0이라는것이고, 폐구간이기 때문에 시작점을 포함해야하니 GetOneCount(l)이 아닌, GetOneCount(l-1)을 빼줘야 한다는 것이다. 

코드에서는 인덱스를 0부터 세기에 1씩 더 빼줬다.

 

분할을 하다가 n이 1이 됐을 때 11011 이기 때문에 룩업테이블을 미리 작성해서 바로 리턴해준다.