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

유사 칸토어 비트열

문제 링크

유사 칸토어 비트열

분석

0번째 비트열은 "1"입니다.
n번째 비트열은 n- 1의 1을 "11011"로 치환하고 0을 "00000"로 치환하여 만듭니다.

예를 들어 다음과 같습니다.

• n = 0 : 1
• n = 1 : 11011
• n = 2 : 11011 11011 00000 11011 11011

n번째 비트열의 길이는 $5^n$입니다.
1의 개수는 $4^n$개입니다.

비트열은 항상 5등분된 구조입니다.
해당 구조에서 3번째는 무조건 0입니다.

l과 r은 1-based입니다.

n번째 유사 칸토어 비트열에서 인덱스 l부터 r까지 구간에 포함된 1의 개수를 구해야합니다.

전체 비트열을 직접 생성하고, 1의 개수를 세어준다는 것은 비효율적이다.
재귀적 접근으로 특정 위치의 값이 1인지 0인지 확인하는 방식으로 해결하는 것이 좋다.

풀이

#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int countOnes(long long n, long long l, long long r)
{
    // 유효하지 않은 구간
    if (l > r)
    {
        return 0;
    }
    // 비트열의 길이가 1인 경우 항상 1을 반환
    if (n == 1)
    {
        return 1;
    }
    
    // 현재 비트열을 5등분하고 n - 1에 대한 비트열의 길이를 저장한다.
    long long len = n / 5;
    // 1의 개수를 저장하는 변수
    long long count = 0;
    
    // 5등분한 구간에 대해 반복
    for (int i = 0; i < 5; ++i)
    {
        // 가운데 구간은 무조건 0이므로 건너뛴다.
        if (i == 2)
        {
            continue;
        }
        
        // 현재 n - 1에 대한 비트열의 i번째 구간의 시작과 끝 인덱스
        long long start = len * i;
        long long end = len * (i + 1) - 1;
        
        // n - 1의 길이와 l, r이 겹치는 범위에서 재귀 호출
        count += countOnes(len, max(l, start) - start, min(r, end) - start);
    }
    
    return count;
}

int solution(int n, long long l, long long r) {
    int answer = 0;
    
    // 비트열의 길이는 5^n이다.
    // l과 r은 1-based이므로 내부적으로는 0-based로 바꾼다.
    answer = countOnes(pow(5, n), l - 1, r - 1);
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n^{log_5 \times 4})$입니다.

• 재귀 함수 $O(n^{log_5 \times 4})$

공간 복잡도는 $O(log_5 n)$입니다.

• 재귀 함수의 깊이 $O(log_5 n)$

테스트 성능

테스트 1 〉 통과 (0.02ms, 4.2MB)
테스트 2 〉 통과 (0.02ms, 4.16MB)
테스트 3 〉 통과 (0.02ms, 3.73MB)
테스트 4 〉 통과 (0.80ms, 3.79MB)
테스트 5 〉 통과 (0.69ms, 4.14MB)
테스트 6 〉 통과 (0.14ms, 4.2MB)
테스트 7 〉 통과 (0.35ms, 4.13MB)
테스트 8 〉 통과 (0.88ms, 3.68MB)
테스트 9 〉 통과 (0.85ms, 4.21MB)
테스트 10 〉 통과 (0.54ms, 4.21MB)
테스트 11 〉 통과 (0.02ms, 4.21MB)
테스트 12 〉 통과 (0.02ms, 4.22MB)
테스트 13 〉 통과 (0.02ms, 3.81MB)
테스트 14 〉 통과 (0.02ms, 4.13MB)
테스트 15 〉 통과 (0.03ms, 4.21MB)