프로그래머스 유사 칸토어 비트열 [Lv. 2] (C++)

프로그래머스

유사 칸토어 비트열의 l번째 부터 r번째 까지 1의 개수를 찾아주세요

(0번째 유사 칸토어 비트열은 1이며 1번째 부터 ~ n번째 까지는 n-1번째 유사 칸토열에서의 1을 11011로 치환하고 0을 00000으로 치환하여 만듭니다.)

 

풀이 방법

#include <string>
#include <vector>
#include <iostream>

using namespace std;
string GetCantorianBit(string str, string zero, int cnt)
{
    while (cnt--)
    {
        str = str + str + zero + str + str;
        zero = zero + zero + zero +zero + zero;
    }
    
    return str;
}

int solution(int n, long long l, long long r) {
    
    string ret = "11011";
    string zero = "00000";
    ret = GetCantorianBit(ret, zero, n-1);

    int answer = 0;
    for (long long i = l-1; i < r; i++)
        if (ret[i] == '1')
            answer++;
    
    return answer;
}

이와같이 string을 이용하여 n번째 유사 칸토어 비트열을 만들어 놓고 1의 개수를 찾는 방식을 생각해 볼 수 있겠지만

시간 초과가 발생하여 해결이 되지 않습니다.

 

해결을 위해서는 조금 더 빠른 방법이 필요합니다.

// 1
// 11011
// 11011 11011 00000 11011 11011
// 11011 11011 00000 11011 11011, 
//		11011 11011 00000 11011 11011, 
//		00000 00000 00000 00000 00000, 
//		11011 11011 00000 11011 11011, 
//		11011 11011 00000 11011 11011

유사 칸토어 비트열을 보면 패턴이 존재합니다.  비트열을 5등분 했을 때, 가운데는 항상 0이 위치하고 있습니다.

이러한 특징을 이용해 1/5를 n번만 탐색하면 해당 위치에 1이 있는지 0이 있는지 체크할 수 있다는 것을 알 수 있습니다.

 

 

n~0까지 탐색하려는 idx가 가운데에 있는지 체크하는 방식으로 풀었습니다.

int GetCantorianBitValue(long long idx, int level)
{
	// level이 0이 될 때 까지 가운데가 아니었다면 1을 반환
    if (level == 0)
        return 1;
    
    // idx가 가운데에 위치한다면 0을 반환
    long long size = pow(5, level); 
    if (size / 5 * 2 <= idx && idx < size / 5 * 3)
        return 0;
    
    // 항상 5등분 하고 있기 때문에 idx를 size / 5 안에 오도록 바꿔줍니다.
    return GetCantorianBitValue(idx % (size / 5), level - 1);
}

이 코드를 l 부터 r까지 탐색하여 1의 개수를 찾아주면 됩니다.

 

 

정답 코드

#include <string>
#include <cmath>
#include <iostream>

using namespace std;

int GetCantorianBitValue(long long idx, int level)
{
    if (level == 0)
        return 1;
    
    long long size = pow(5, level); 
    if (size / 5 * 2 <= idx && idx < size / 5 * 3)
        return 0;
    
    return GetCantorianBitValue(idx % (size / 5), level - 1);
}

int solution(int n, long long l, long long r) {
    int answer = 0;
    for (long long i = l -1; i < r; i++)
        answer += GetCantorianBitValue(i, n);
    
    return answer;
}