catsridingCATSRIDING|OCEANWAVES
Challenges

프로그래머스 | Level 2 | 유사 칸토어 비트열

jynn@catsriding.com
Nov 07, 2024
Published byJynn
999
프로그래머스 | Level 2 | 유사 칸토어 비트열

Programmers | Level 2 | 유사 칸토어 비트열

Problems

  • 📘 Src: Programmers
  • 🗂️ Cat: Divide and Conquer

󰧭 Description

수학에서 칸토어 집합은 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() 함수를 완성해주세요.

 Constraints

  • 1 ≤ n ≤ 20
  • 1 ≤ l, r ≤ 5^n
    • l ≤ r < l + 10,000,000
    • l과 r은 비트열에서의 인덱스(1-base)이며 폐구간 [l, r]을 나타냅니다.

󰦕 Examples

nlrresult
24178

Solutions

󰘦 Code

Solution.java
import java.util.*;

class Solution {
    public int solution(int n, long l, long r) {
        return dac(n, l - 1, r - 1);  // 입력을 0-based index로 변환
    }
    
    private int dac(int depth, long rangeStart, long rangeEnd) {
        if (depth == 0) return 1;  // base case: depth가 0일 때는 '1'로만 구성
        
        int count = 0;  // 1의 개수 카운트
        long segLength = (long) Math.pow(5, depth - 1);  // 현재 깊이의 각 segment 길이 계산
        
        for (int i = 0; i < 5; i++) {
            long segStart = segLength * i;      // 현재 segment의 시작 위치
            long segEnd = segStart + segLength - 1;  // 현재 segment의 종료 위치
            
            if (i == 2) continue;  // 중앙 segment는 모두 0이므로 건너뜀
            if (rangeStart > segEnd || rangeEnd < segStart) continue;  // 현재 구간과 겹치지 않으면 건너뜀
            
            if (segStart >= rangeStart && segEnd <= rangeEnd) count += dac(depth - 1, 0, segLength - 1);  // segment 전체가 구간에 포함될 때
            else count += dac(depth - 1, Math.max(0, rangeStart - segStart), Math.min(segLength - 1, rangeEnd - segStart));  // 부분 구간
        }
        return count;
    }
}

 Approaches

유사 칸토어 비트열 문제는 칸토어 집합의 개념을 바탕으로 하여 재귀적으로 비트열을 확장하고, 주어진 구간에 포함된 1의 개수를 계산하는 문제입니다. 이 문제는 5진수의 수학적 규칙을 활용할 수도 있지만, 여기서는 분할 정복(Divide and Conquer)과 재귀적(Recursive) 접근 방식을 통해 구간을 효율적으로 탐색하는 해결 방식을 살펴보겠습니다.

1. 문제 분석

이 문제는 n단계의 유사 칸토어 비트열에서 특정 구간에 포함된 1의 개수를 찾는 문제입니다. 유사 칸토어 비트열은 각 단계마다 이전 비트열의 1과 0을 고정된 패턴으로 치환하며 확장하는 특성을 가지고 있으며, 단계가 증가할수록 그 길이가 급격히 커집니다. 주어진 단계 n에서 전체 비트열의 길이는 5^n에 이르게 됩니다. 따라서, n이 커질수록 전체 비트열을 직접 생성하여 구간 내 1의 개수를 계산하는 방식은 비효율적이고, 문제의 시간 복잡도 제한을 넘기게 됩니다. 이러한 특성으로 인해, 이 문제는 모든 비트열을 생성하지 않고 필요한 구간만 재귀적으로 나누어 탐색하는, 분할 정복 접근 방식이 필요합니다.

유사 칸토어 비트열은 특정 규칙에 따라 다섯 개의 구간으로 나뉘며, 각 단계에서 1과 0이 고정된 패턴으로 치환됩니다. 즉, 비트열에서 1은 "11011"로 치환되고 0은 "00000"으로 치환되므로, 결과적으로 각 단계마다 비트열의 길이가 다섯 배로 확장됩니다. 이 다섯 개의 구간에서 세 번째 구간은 항상 "00000"으로만 이루어져 1을 포함하지 않으므로 탐색 과정에서 이 구간을 생략할 수 있습니다. 이러한 성질을 활용하면 탐색 범위를 최적화할 수 있으며, 전체 탐색을 수행하지 않고도 빠르게 원하는 구간에서 1의 개수를 구할 수 있습니다.

효율적인 해결을 위해 주어진 구간 [l, r]이 포함된 부분에만 접근하여 구간을 재귀적으로 나누고, 각 구간이 1 또는 0을 포함하는 특성을 활용합니다. 탐색할 구간을 다섯 개로 나누어 중앙 구간을 생략하고, 나머지 구간이 주어진 구간과 겹치는지 확인하여 필요한 경우에만 재귀적으로 세분화된 탐색을 수행합니다. 이 과정에서 구간이 최종적으로 1로만 이루어진 가장 작은 단위에 도달하면, 해당 구간 내 1의 개수를 세어 반환하게 됩니다.

2. 접근 방식

문제를 효율적으로 해결하기 위해 각 목표 구간에 대해 다음과 같은 단계로 접근합니다.

  1. 재귀적 탐색을 통한 구간 분할: n단계의 유사 칸토어 비트열은 다섯 개의 구간으로 나뉩니다. 각 구간은 이전 단계의 비트열을 다섯 번 복제한 형태로 구성되며, 비트열을 확장할 때 1은 "11011"로, 0은 "00000"으로 치환됩니다. 이 중에서 세 번째 구간은 항상 "00000"으로만 이루어져 있어 1이 포함될 가능성이 없으므로, 주어진 탐색 구간이 이 중앙 구간에 해당할 경우 탐색을 건너뛰어 효율성을 높일 수 있습니다.
  2. 구간 분할을 통한 재귀 호출: 현재 단계에서 다섯 개의 하위 구간을 정의하고, 주어진 구간 [l, r]과 겹치는지 확인합니다. 하위 구간이 탐색 구간과 겹치지 않는다면 재귀 호출을 생략하고 넘어가며, 겹치는 경우에만 더 작은 단위로 계속 분할합니다. 이 과정은 각 단계에서 구간을 다섯 부분으로 세분화하며, 하위 구간이 탐색 구간에 완전히 포함될 때까지 재귀적으로 반복합니다.
  3. 기저 조건 처리: 재귀적으로 구간을 나누다 보면 가장 작은 단위인 0번째 단계에 도달합니다. 이 단계에서는 비트열의 길이가 1이 되어 더 이상 분할할 수 없으며, 이때 구간에 1이 포함되어 있는지 확인하여 결과를 반환합니다. 이 기저 조건을 통해 재귀 탐색이 종료됩니다.
  4. 최소 범위 내 구간 합산: 각 재귀 호출은 탐색 중인 하위 구간이 주어진 구간 내에 완전히 포함되었는지 확인하여 필요한 개수만큼 1을 빠르게 합산합니다. 하위 구간이 탐색 구간에 일부만 포함되는 경우, 포함된 범위에 해당하는 부분만 재귀적으로 탐색하여 1의 개수를 누적합니다. 이 방식으로 중간 단계의 탐색 범위를 줄여가며 최종적으로 1의 개수를 구합니다.

이 접근 방식을 통해 각 단계에서 불필요한 계산을 줄이고, 주어진 구간 내 1의 개수를 효율적으로 찾을 수 있습니다.

3. 작업 초기화 및 구간 인덱스 변환

유사 칸토어 비트열의 구간은 문제에서 1부터 시작하는 인덱스 기준으로 주어지므로, 이를 0부터 시작하는 인덱스 기준으로 변환합니다. 구간의 시작과 끝 인덱스를 각각 1을 뺀 값으로 조정하여, 이후의 탐색 과정에서 사용할 수 있도록 합니다. 이렇게 변환된 인덱스를 통해, 재귀적 탐색 함수에서도 정확한 구간 참조가 가능합니다.

Solution.java
// 범위를 0-based index로 변환
long rangeStart = l - 1;
long rangeEnd = r - 1;
4. 다섯 개의 구간 분할 및 재귀 호출

유사 칸토어 비트열의 각 단계는 다섯 개의 세그먼트로 나누어지며, 각 구간에서 1의 개수를 계산하기 위해 재귀적으로 탐색을 수행합니다.

  1. 기저 조건: 탐색의 깊이가 0에 도달하면, 현재 구간은 길이가 1인 기본 단위가 됩니다. 이때의 구간은 항상 1로만 구성되므로, 이 값 1을 반환하여 1의 개수를 누적합니다.
  2. 구간 분할 및 조건 확인: 현재 탐색 깊이가 1 이상일 경우, 전체 구간을 다섯 개의 세그먼트로 나누어 탐색을 진행합니다. 이때 각 세그먼트의 길이는 5의 제곱수 형태로 정의되며, 다섯 개 세그먼트 중 세 번째 세그먼트는 "00000"으로만 구성되어 있어 1을 포함하지 않으므로 바로 건너뜁니다.
  3. 재귀 호출: 현재 탐색 구간과 세그먼트가 겹치는 경우에만 재귀적으로 탐색을 진행합니다. 만약 세그먼트가 탐색 구간에 완전히 포함될 경우, 해당 세그먼트 전체를 탐색하고, 세그먼트가 부분적으로 포함될 경우에는 구간을 세분화하여 재귀적으로 탐색 범위를 좁혀나갑니다. 이를 통해 각 단계에서 구간이 좁혀질수록 탐색 구간의 범위도 점차 줄어들며 1의 개수를 효율적으로 누적할 수 있습니다.
Solution.java
private int dac(int depth, long rangeStart, long rangeEnd) {
    if (depth == 0) return 1;  // 기저조건: depth가 0일 때는 '1'로만 구성
    
    int count = 0;  // 1의 개수 카운트
    long segLength = (long) Math.pow(5, depth - 1);  // 현재 깊이의 각 segment 길이 계산

    for (int i = 0; i < 5; i++) {
        long segStart = segLength * i;      // 현재 segment의 시작 위치
        long segEnd = segStart + segLength - 1;  // 현재 segment의 종료 위치
        
        if (i == 2) continue;  // 3번째 segment는 "00000"으로만 구성되므로 건너뜀
        if (rangeStart > segEnd || rangeEnd < segStart) continue;  // 현재 구간과 겹치지 않으면 건너뜀
        
        // segment가 전체 탐색 구간에 포함되는 경우
        if (segStart >= rangeStart && segEnd <= rangeEnd) {
            count += dac(depth - 1, 0, segLength - 1);  // 재귀적으로 전체 구간 탐색
        } else {
            // segment가 탐색 구간에 일부 포함되는 경우
            count += dac(depth - 1, Math.max(0, rangeStart - segStart), Math.min(segLength - 1, rangeEnd - segStart));
        }
    }
    return count;  // 현재 구간에서 누적된 1의 개수를 반환
}
5. 최종 결과 반환

모든 구간에 대한 탐색이 완료되면, 재귀적 탐색 함수는 주어진 구간 내의 1의 개수를 반환합니다. 최종적으로 이 값을 반환하여, 주어진 범위 내 1의 개수를 출력합니다.

Solution.java
// 모든 탐색을 수행하고 최종 결과 반환
return dac(n, l - 1, r - 1);

이러한 접근을 통해 주어진 구간 내의 1의 개수를 효율적으로 찾을 수 있습니다.

󰄉 Complexity

  • ⏳ TC: O(log N)
  • 💾 SC: O(log N)

이 코드는 효율적으로 구간 내 1의 개수를 계산하기 위해 재귀와 분할 정복을 사용하며, 문제의 시간 제한과 공간 제한을 모두 만족합니다.

  • Algorithm
  • Divide and Conquer