문제설명
문제분석
유사 칸토어 비트열을 생성하고, 해당 비트열의 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이기 때문에 모두 카운트합니다. 오늘도 새로운 시선을 눈에 담아봅니다.
'Practice for coding test' 카테고리의 다른 글
프로그래머스 - Level 2. 덧칠하기 / JavaScript (js) (0) | 2023.03.07 |
---|---|
프로그래머스 - Level 2. 숫자 변환하기 / JavaScript (js) (0) | 2023.03.06 |
프로그래머스 - Level 2. 2개 이하로 다른 비트 / JavaScript (js) (0) | 2023.03.04 |
프로그래머스 - Level 2. k진수에서 소수 개수 구하기 / JavaScript (js) (0) | 2023.03.03 |
프로그래머스 - Level 2. [1차] 뉴스 클러스터링 / JavaScript (js) (0) | 2023.03.02 |