C++:: 프로그래머스 < 유사 칸토어 비트열 >

문제자체를 이해하는데 오래걸렸고 처음풀이와 두번째풀이를 각각 직접 문자열로 만들어서 체크, 단순 재귀로 풀어서 시간초과가 나와 실패했었다.
때문에 구간을 나누어서 0일때는 아예 재귀를 안타게끔 풀이를 바꿔서 풀었다.
n = 1: 11011
n = 2: 11011 11011 00000 11011 11011
n = 3: 1101111011000001101111011 1101111011000001101111011 00000...... 1101111011000001101111011
필자의 풀이의 핵심은
n 번째 칸토어 비트열은 5구간으로 나누었을때 n-1번째 칸토어 비트열이 3번째 구간 빼고 존재한다는 점이다(3번째 구간은 전부 0으로 이루어져있음). 때문에 3번째 구간에대한 재귀는 생략하였고, 시작과 끝지점을 나누어서 재귀를 타주었다.(시작 끝이 n-1일때 같은 구간에서 파생되었다면 재귀를 따로 해주지않고 한번에 한다.)

#include <string>
#include <vector>
#include <cmath>
using namespace std;

int answer = 0;

void recur(int n, long long l, long long r)
{
    long long range = 1LL * pow(5,n-1);//n번째 유사 칸토어 비트열길이를 5구간으로 나눈 길이
    int s = l/range, e = r/range;// 몇번째 구간에 존재하는지
    if(n==1)
    {
        for(int i=l;i<=r;i++) if(i!=2) answer++;// n==1 일때 칸토어 비트열은 11011이므로
        return ;
    }
    for(int i=s+1;i<e;i++) if(i!=2) answer += (int)pow(4,n-1);// 시작 구간과 종료구간 사이의 값++
    if (s == e) recur(n-1, l - range*s, r - range*e);// 시작 종료 구간이 동일하다면
    else
    {
        if(s!=2) recur(n-1, l - range*s, range-1);//3번째 구간이 아니라면 시작구간 에서 range - 1까지
        if(e!=2) recur(n-1, 0,r - range*e);//3번째 구간이 아니라면 0에서 종료구간까지
    }
}

int solution(int n, long long l, long long r)
{
    recur(n,--l,--r);
    return answer;
}

삼항연산자를 사용하여 좀더 간결하게 구현한 코드도 존재한다. 하지만 분할하지않고 재귀를 타서 시간복잡도는 필자의 코드보다 크다.

#include <bits/stdc++.h>
using namespace std;

int f(int n, long long x)
{
    return n == 1 ? x % 5 != 2 : f(n - 1, x / 5) ? x % 5 != 2 : 0;
}
int solution(int n, long long l, long long r)
{
    int answer = 0;
    for(long long i = l - 1; i < r; i++) answer += f(n, i);
    return answer;
}