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

---

📌 문제 설명

수학에서 칸토어 집합은 0과 1 사이의 실수로 이루어진 집합으로, [0, 1]부터 시작하여 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만들어집니다.

남아는 칸토어 집합을 조금 변형하여 유사 칸토어 비트열을 만들었습니다. 유사 칸토어 비트열은 다음과 같이 정의됩니다.

• 0 번째 유사 칸토어 비트열은 "1" 입니다.
• n(1 ≤ n) 번째 유사 칸토어 비트열은 n - 1 번째 유사 칸토어 비트열에서의 1을 11011로 치환하고 0을 00000로 치환하여 만듭니다.

남아는 n번째 유사 칸토어 비트열에서 특정 구간 내의 1의 개수가 몇 개인지 궁금해졌습니다.
n과 1의 개수가 몇 개인지 알고 싶은 구간을 나타내는 l, r이 주어졌을 때 그 구간 내의 1의 개수를 return 하도록 solution 함수를 완성해주세요.

 

📌 제한 사항

• 1 ≤ n ≤ 20
• 1 ≤ l, r ≤ 5n
• l ≤ r < l + 10,000,000
• l과 r은 비트열에서의 인덱스(1-base)이며 폐구간 [l, r]을 나타냅니다.

🔗 문제 링크

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

프로그래머스

---

반응형

728x90

👩‍💻 코드

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

using namespace std;

int solution(int n, long long l, long long r) {
    if (n == 0){
        return 1;
    }
    
    int answer = 0;
    long long length = 1;
    
    for (int i=0; i<n; i++){
        length *= 5;
    }
    
    for (long long i=l-1; i<r; i++){
        long long index = i;
        bool isOne = true;
        
        for (long long div=length; div > 1; div /= 5){
            if ((index / (div / 5)) % 5 == 2){
                isOne = false;
                break;
            }
            index %= (div / 5);
        }
        
        if(isOne){
            answer++;
        }
    }
    
    return answer;
}

---

📝 풀이

유사 칸토어 비트열은 5^n의 길이인 재귀적으로 반복되는 패턴을 갖게 됩니다.

"11011" 패턴의 중앙에 위치하는 0과 "00000"으로 치환된 구간의 모든 0들을 제외하면 1이 됩니다.

 

이를 활용하여 현재 구간의 중앙에 위치(5로 나눈 나머지가 2)하면 0이 됩니다.

중앙에 위치하지 않은 경우 계속하여 구간을 나누어 index의 위치를 재조정합니다.

 

0이 아닌 경우, 즉 1인 경우는 answer을 증가시킵니다.

최종적으로 answer을 return 합니다.