[프로그래머스/C++] 유사 칸토어 비트열

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제에서 나오는 수열은 프랙탈 구조처럼 일정한 규칙을 갖고있는 수열이다.

 

만약 이 문제에서 1의 개수를 직접 count한다면 최대 개수가 5^20 이기 때문에 시간복잡도에서 문제가 생길 수 있다.

 

그러므로 규칙을 이용해 1의 개수를 직접 세지 않고, 범위를 이용해 빠르게 풀었다.

 

일단 l ~ r까지 1의 개수를 구하기 위해 생각해 볼 것은 n = i 인 경우의 모든 1의 개수와 n = i -1 인 경우의 모든 1의 개수는 총 4배 차이가 난다.

 

왜냐하면 이전 배열의 1이 11011로 바뀌고 0은 00000으로 바뀐다. 그러므로 1의 개수는 이전의 1의 개수에만 영향을 받아 4배씩 증가하는 것이다.

 

그리고 [l , r] 까지의 1의 개수는 [1, r] 구간의 1의 개수에서 [1,  l - 1] 구간의 1의 개수를 빼서 구할 수 있다.

 

이제 두 사실을 이용해 문제를 해결하는데, 아래 그림을 참고해 보자

 n이 2인경우에 아래와 같이 칸토어 비트열이 만들어진다.

 

이때, 1~9 구간의 1의 개수를 구하려면 어떻게 해야할까?

 

칸토어 비트열은 한 숫자가 5개의 숫자로 바뀌므로 9를 5로 나누어 몫과 나머지를 이용해 1의 개수를 구할 수 있다.

 

먼저 9를 5로 나누면 몫은 1이 된다.

이 몫의 의미는 (n-1)의 칸토어 비트열의 [1, 1] 구간을 포함한다는 의미가 된다.

 

그리고 나머지는 4가 나오는데, 이 4는 [1, 1, 0, 1, 1] 또는 [0, 0, 0, 0, 0] 의 4번째 숫자까지 포함한다는 의미가 된다.

그렇다면 나머지가 가리키는 비트열이 [1, 1, 0, 1, 1]인지 [0, 0, 0, 0, 0,]는 어떻게 구분할까?

 

이는 몫을 이용해 구분할 수 있다.

9의 몫이 1이였고, 나머지는 그 다음 구간은 2번째 구간을 의미한다.

그러므로 2번째 구간은 1에서 파생된 칸토어 비트열이기 때문에 [1, 1, 0, 1, 1]이고, 4번째 수까지 1의 개수를 구하면 3이 된다.

 

이를 이용해 구간 [1, 9]의 1의 개수는 4+3=7 이다.

 

마찬가지로 구간 [1, 14]의 1의 개수를 구하면 몫이 2, 나머지는 4이다.

몫이 2 이므로 2 * 4 ([1,1,0,1,1] 구간이 2개 있다는 뜻)이고, 몫이 2이므로 다음 구간은 3번째 구간이다.

 

3번째 구간은 0으로 파생 기 때문에 [0, 0, 0, 0, 0]이고 4번째 수까지의 1의 개수를 구하면 0이 된다.

그러므로 8+0=8 이다.

 

이를 이용해 구간 [9, 14]의 1의 개수는 8-7=1 임을 계산 할 수 있다.

 

+ n이 늘어나도 마찬가지로 몫을 구한 뒤, 나머지가 1로 파생된 구간인지 0에서 파생된 구간인지를 계산해 return해주면 된다.

즉, i - 1 단계의 나머지가 0으로 파생된 구간이라면, i 단계의 나머지도 0으로부터 파생된 구간이므로 그 구간에 1의 개수는 0이 된다.

 

 

​

[아이디어 정리]

1. n이 1 늘어날 때 마다 1의 총 개수가 4배씩 늘어난다.
2. 구간의 1의 개수를 구하는 방법은 [1, r]구간의 1의 개수 - [1, l-1]구간의 1의 개수로 구한다.
3. n이 i인 경우에 [1, k] 구간의 1의 개수는 [1, k/5] 구간의 1의 개수 * 4 + [k - (k%5), k]의 1의 개수와 같다. 
4. [k - (k%5), k] 구간이 [1, 1, 0, 1, 1]인지 [0, 0, 0, 0, 0]인지는 어떤 수에서 파생됐는지로 알 수 있다.

 

 

Code

 

 

#include <string>
#include <vector>

using namespace std;

int exReturn(int a){// 나머지 계산
    if (a>2)
        return a-1;
    else
        return a;
}

vector<long long> calc(int n, long long targetNum) // targetNum번째 수를 포함했을 때, 1번째 부터 targetNum번째 수까지 1의 개수를 return
{
    vector<long long> nv(2,0);
    if (n==1)
    {
        if (targetNum!=2){
            nv[1]=1;
        }
        nv[0]=exReturn(targetNum);
        return nv;
    }
    else
    {
        long long nextNum=targetNum/5;
        int extNum=targetNum%5;
        nv=calc(n-1,nextNum);
        nv[0]*=4;
        if (nv[1]==1)
        {
            nv[0]+=exReturn(extNum);
        }
        nv[1] = ((extNum==2||nv[1]==0)?0:1); // 나머지가 2이거나 이전 수가 0에서 만들어졌다면 0
    }
    return nv;
}    


int solution(int n, long long l, long long r) {
    vector<long long> c = calc(n,l-1);
    vector<long long> d = calc(n,r);
    return d[0]-c[0];
}

 

---

구간의 1의 개수를 뺀다는 아이디어는 빠르게 생각했는데, 나머지를 계산하는 방법을 생각하느라 시간이 걸렸다.

5로 나누어 계산할게 아니라 5^(n-1)씩 계산해 재귀적으로 구했다면 더 편했을 것 같다...

생각보다 난이도가 있는 문제였다.

 

프로그래머스