프로그래머스 - Level 2. 유사 칸토어 비트열 / JavaScript (js)

문제설명

문제분석

유사 칸토어 비트열을 생성하고, 해당 비트열의 l부터 r에 포함된 1의 갯수를 리턴하는 문제입니다. 최초 접근은 문제에서 요구한 대로 n-1번째의 "1"을 "11011"로, "0"을 "00000"으로 치환해 f(n)을 구해 slice(l-1, r)로 범위를 구하고 1을 카운트했습니다.

이해하기 쉽게 코드작성하기

function solution(n, l, r) {
    const similarContorBits = getSimilarCantorBits(n);
    return countOnes(similarContorBits.slice(l - 1, r));
}

function getSimilarCantorBits(n) {
    let bits = "1";
    if(n === 0) return bits;
    
    for(let i = 0; i < n; i++) {
        bits = bits.split("").map(x => x === "1" ? x.replaceAll("1", "11011") : x.replaceAll("0", "00000")).join("")
    }
    
    return bits;
}

function countOnes(bits) {
    if(bits.length === 0) return 0;
    return bits.replaceAll("0", "").length;
}

당연히 이 접근으로는 테스트 케이스 중 시간 초과가 발생되는 때가 있을 것이라 생각했고, 아니나 다를까 에러를 뱉습니다.

이 문제를 표로 나타내보고, 문제 해결의 실마리를 얻을 수 있었습니다.

n	bits	length	# of 1's
0	"1"	1 * 5^0	1 * 4^0
1	"11011"	5^1	4^1
2	"1101111011000001101111011"	5^2	4^2
3	"11011110110000011011110111101111011000001101111011000000000000000000000000011011110110000011011110111101111011000001101111011"	5^3	4^3
4	"1101111011000001101111011110111101100000110111101100000000000000000000000001101111011000001101111011110111101100000110111101111011110110000011011110111101111011000001101111011000000000000000000000000011011110110000011011110111101111011000001101111011000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001101111011000001101111011110111101100000110111101100000000000000000000000001101111011000001101111011110111101100000110111101111011110110000011011110111101111011000001101111011000000000000000000000000011011110110000011011110111101111011000001101111011"	5^4	4^4

작성된 것을 보면, n이 늘어날 때마다 bits의 길이는 5^n이 됩니다. 마찬가지로 포함된 1의 총 갯수는 4^n이 됩니다. 이 이유는 간단합니다.

먼저 n이 1일때를 보면 비트가 "11011"입니다. 따라서 길이는 5이고, 1의 갯수는 4입니다. n이 1 늘어나면 "1" 대신 "11011"을 넣게 됩니다. 따라서 n이 2가될 때는 다음과 같습니다.

f(2) = f(1) + f(1) + "00000" + f(1) + f(1)

이 내용으로 일반항을 구하면 다음과 같습니다.

f(n) = f(n-1) + f(n-1) + "0".repeat(5^(n-1)) + f(n-1) + f(n-1)

결국, f(n)의 bits를 5개로 쪼갤 수 있고, 이때 1, 2, 4, 5번째는 f(n-1)이 들어가고, 3인 경우에는 "0"이 f(n-1)의 길이만큼 들어가게 됩니다.

일단 테스트케이스가 짧은 경우는 기존 문제대로 해결하고, 긴 경우에는 다른 로직을 접하는 형태로 문제를 해결해보겠습니다.

 

function solution(n, l, r) {
    if(n <= 5) return countOnes(getSimilarCantorBits(n).slice(l-1, r));
    return getOnes(n, r) - getOnes(n, l-1);
}

funtion getOnes(n, l) {
	// TODO:
}

function getSimilarCantorBits(n) {
    let bits = "1";
    if(n === 0) return bits;
    
    for(let i = 0; i < n; i++) {
        bits = bits.split("").map(x => x === "1" ? x.replaceAll("1", "11011") : x.replaceAll("0", "00000")).join("")
    }
    
    return bits;
}

function countOnes(bits) {
    if(bits.length === 0) return 0;
    return bits.replaceAll("0", "").length;
}

이제 생성할 getOnes는 0부터 l까지에 포함된 1의 갯수를 계산합니다.

값을 n-1번째의 총길이로 나눈 몫과 나머지를 이용합니다. 이때 몫이 2보다 큰 경우, "0"으로 이루어진 부분을 반드시 만나게 됩니다. 따라서 몫이 2보다 큰 경우에는 몫에 1을 빼줘야 합니다.

function getOnes(n, l) {
    const arr = [1, 2, 2, 3, 4];
    let AllOnesUntilL = 0;
    let remains = 0;
    do {
        if(n === 1) {
            AllOnesUntilL += arr[l - 1];
            break;
        }
        if(l === 0) break;
        const AllengthForN = Math.pow(5, n-1);
        let q = Math.floor(l / AllengthForN);
        remains = q === 2 ? 0 : l % AllengthForN;
        q = q > 2 ? q - 1 : q;
        
        AllOnesUntilL += q * Math.pow(4, n-1);
        if(remains === 0) break;
        l = remains;
        n--;
    } while(n > 0)
    
    return AllOnesUntilL;
}

이때 몫 * 4^(n-1)만큼 1이 존재하기 때문에 결과를 업데이트합니다. 이후 n이 1이 될때까지 반복합니다.

 

----

 

이 문제를 해결하고서도 좀 찝찝하기도 해서 다른 사람의 풀이를 참고해봤습니다. 그런데 어마어마한 풀이를 봐버렸습니다.

function solution(n, l, r) {
    let answer = 0;
    for (let i = l - 1; i <=r - 1; i++) {
        if (!i.toString(5).match('2')) answer += 1;
    }
    return answer;
}

이 풀이를 해석하자면, l-1부터 r-1까지 순회하면서 각 숫자를 5진수로 변환합니다. 이때의 숫자가 만약 2를 포함하는 경우("11011"의 0을 나타내는 경우)를 제외하면 1이기 때문에 모두 카운트합니다. 오늘도 새로운 시선을 눈에 담아봅니다.