🎯문제
수학에서 칸토어 집합은 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]을 나타냅니다.
- l ≤
입출력 예
| n | l | r | result |
|---|---|---|---|
| 2 | 4 | 17 | 8 |
입출력 예 설명
2 번째 유사 칸토어 비트열은 "1101111011000001101111011" 입니다. 음영 표시된 부분은 폐구간 [4, 17] 이며 구간 내의 1은 8개 있습니다.
✏️풀이
코드
class Solution {
// dfs 탐색 메소드
public int count(int n, long l, long r, long index) {
// n이 0일 때
if(n == 0) {
return 1;
}
int num = 0;
// 수의 길이를 구해줌
long part = (long)Math.pow(5, n-1);
for(int i = 0; i < 5; i++) {
// 가운데, 즉 0이거나 범위 밖일 경우
if(i == 2 || r < (index + part * i) || (index + part * (i + 1) - 1) < l) {
continue;
}
// 탐색을 진행하여 반환된 값을 더함
num += count(n - 1, l, r, index + part * i);
}
return num;
}
public int solution(int n, long l, long r) {
return count(n, l, r, 1);
}
}설명
dfs 탐색을 사용하여 진행하였다.
dfs 탐색 메소드의 매개변수는 다음과 같다.
- int n
- 비트열의 반복 횟수
- long l
- 폐구간 시작점
- long r
- 폐구간 종료점
- long index
- 탐색 위치
n은 0일 때 유사 칸토어 비트열은 1이며 1의 개수도 단 하나밖에 없기 때문에 1을 반환해준다.
n이 0이 아닐 경우 num 변수에 구간 안에 있는 1의 개수를 저장하여 반환해주는데, 이때 수의 길이는 5의 n-1 제곱을 계산하여 구할 수 있다.
유사 칸토어 비트열은 11011, 11011/11011/00000/11011/11011, ... 처럼 늘어나게 된다.
이를 사용해서 가운데 0이 되는 부분을 제외하고 1이 나오는 부분들 중 구간 안에 포함되는 부분들만 체크를 해주면 된다.
if문을 활용하여 i == 2일 때 즉, 11011에서 0일 때 값이거나 범위 밖에 있는 값일 경우에는 continue를 해주고, 범위 안에 있는 값일 경우 탐색을 진행한다.
모든 탐색이 진행된 뒤 나온 값을 반환을 한다.
solution 메소드에서는 count 메소드를 호출하고, count 메소드에서 반환된 값을 그대로 return 해주면 문제를 해결할 수 있다!
💡느낀 점
dfs 탐색 관련 문제들을 많이 풀어봤지만 dfs 탐색을 사용해야겠다는 생각이 쉽게 들지 않았던 문제였다. 아직 문제 경험이 부족해서 그런 거일수도 있지만 흔히 알고 있는 정형화된 방식이 아니라 약간의 변형을 해주어서 사용한 느낌이라 색다르고 어렵게 풀었던 문제였다..
링크
