프로그래머스 Lv.2 유사 칸토어 비트열
문제 설명
수학에서 칸토어 집합은 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≤ 5^n
- l ≤
r<l+ 10,000,000l과r은 비트열에서의 인덱스(1-base)이며 폐구간 [l, r]을 나타냅니다.입출력 예
n l r result 2 4 17 8
풀이 코드
function solution(n, l, r) {
const calcBit = (index) => {
let exp = 0;
let result = 0;
while (index > 5 ** (exp + 1)) exp++;
if (exp === 0) return index < 3 ? index : index - 1;
const quotient = Math.floor(index / 5 ** exp);
const remainder = quotient + 1 !== 3 ? index % 5 ** exp : 0;
if (quotient >= 3) result += (quotient - 1) * 4 ** exp;
else result += quotient * 4 ** exp;
return result + calcBit(remainder);
};
return calcBit(r) - calcBit(l - 1);
}
풀이 설명
- 5^n까지의 전체 1의 개수는 4^n 개이다.
- 폐구간 [a, b]는 a와 b를 포함한 사이 구간이다.
function solution(n, l, r) {
const calcBit = (index) => {
let exp = 0;
let result = 0;
while (index > 5 ** (exp + 1)) exp++;
if (exp === 0) return index < 3 ? index : index - 1;
//...
};
//...
}
calcBit는 index를 매개변수로 받아 처음부터 해당 인덱스까지의 1의 개수를 반환한다.
-
index보다 크지 않은 5^n의 가장 큰 n(=exp)를 구한다.(e.g. index가 17이면, 5^1보다는 크고 5^2보다는 작으므로 exp는 1이다.)
-
exp가 0일 경우에는 구하려는 수(=index)가 5보다 작다는 뜻이므로 1의 개수를 구할 때 4^n이 통하지 않는다. 아래와 같은 방법으로 재귀를 종료한다.index< 3 → 1의 개수는 index와 동일index>= 3 → 1의 개수는index- 1 (11011에서 3번째는 항상 0)
function solution(n, l, r) {
const calcBit = (index) => {
//...
const quotient = Math.floor(index / 5 ** exp);
const remainder = quotient + 1 !== 3 ? index % 5 ** exp : 0;
if (quotient >= 3) result += (quotient - 1) * 4 ** exp;
else result += quotient * 4 ** exp;
return result + calcBit(remainder);
};
return calcBit(r) - calcBit(l - 1);
}
quotient는 index를 아까 구한 5^exp로 나눈 몫이다. (e.g. 17인 경우 5^1로 나눈 몫은 2)
remainder는 두 가지로 나눌 수 있다.
-
quotient가 2인 경우: 나머지는 항상 3번째 범주 안에 들기 때문에 모두 0이므로 0을 저장 -
그 이외의 경우:
index를 5^exp로 나눈 나머지를 저장
quotient가 3 이상인 경우, 몫에 3번째 0의 범주 1을 빼고 4^exp를 곱한 수를 결괏값에 저장하고 3 미만인 경우, 몫과 4^exp를 곱한 수를 저장한다. 나머지가 5보다 작을 때까지 재귀로 돌린다.
r에 대한 calcBit의 결과에서 (l - 1)에 대한 calcBit 결과를 리턴한다. (폐구간의 인덱스도 포함하므로 l의 이전 인덱스까지의 값을 제거한다.)
References
프로그래머스 연습