[ 프로그래머스 ] 148652 유사 칸토어 비트열

Link | 프로그래머스 148652번 문제 : 유사 칸토어 비트

📌 About

1을 0번째로 하여 한 번의 연산에서 1은 11011으로 0은 00000으로 변환하면 된다.

1 -> 11011 -> 1101111011000001101111011 -> ... 와 같이 변환이 된다.

그런데 최대 길이가 $5^20$ 이기 때문에 전체 변환을 하면 메모리 초과가 발생한다.

실제로 다음과 같이 구현을 했더니 메모리 초과가 발생하였다.

public int solution(int n, long l, long r) {
    String bits = "1";
    while (n-- > 0)
        bits = bits.chars()
                .mapToObj(bit -> bit == '1' ? "11011" : "00000")
                .collect(Collectors.joining());
    long idx = 1;
    int count = 0;
    for (char bit : bits.toCharArray()) {
        if (l <= idx && idx <= r && bit == '1') count++;
        idx++;
    }
    return count;
}

그렇기 때문에 이 문제는 분할 정복으로 하면서 불피요한 범위는 버려야 한다.

📌 Solution

분할에서 필요한 정보는 3가지이다.

분할된 위치의 비트열, 분할된 범위, 구하고자하는 범위이다.

이 정보들은 다음과 같이 표현할 수 있다.

public int countOnes(String bits, long s, long e, long l, long r, int n) {}

bits는 현재 분할된 비트열이다.

11011 비트열은 11011, 11011, 00000, 11011, 11011 라는 5개의 비트열로 분할된다.

s는 현재 비트열의 시작 위치, e는 현재 비트열의 종료 위치로 최종 연산의 비트열 범위값이다.

l, r, n은 주어진 값이다.

만약 2번의 연산을 한다면 최종 범위는 1부터 $5^2$ 까지이다.

첫 번째 연산으로 11011이 나올 것이며 이는 1 ~ $5^2$의 범위 비트열이다.

두 번째 연산에서는 각각 1 ~ 5, 6 ~ 10, 11 ~ 15, 16 ~ 20, 21 ~ 25의 범위로 분할될것이다.

그림으로 나타내면 다음과 같다.

계산하는 방법은 다음과 같다.

for (int i = 0; i < 5; i++) {
    String bitsTemp = bits.charAt(i) == '1' ? "11011" : "00000";
    long sTemp = s + ((e - s + 1) / 5 * i);
    long eTemp = s + ((e - s + 1) / 5 * (i + 1)) - 1;
    
	if (r < sTemp || l > eTemp || bitsTemp.equals("00000")) continue;
    sum += countOnes(bitsTemp, sTemp, eTemp, l, r, n - 1);
}

bits, s, e는 현재 비트열의 정보이고 temp 값들은 다음 비트열의 정보이다.

비트열의 길이는 무조건 5이다. (비트 하나가 비트 5개로 변환하기 때문)

비트열의 변환은 5개의 비트들을 차례대로 탐색하며 이루어진다.

비트가 1이면 11011으로 0이면 00000으로 변환한다.

String bitsTemp = bits.charAt(i) == '1' ? "11011" : "00000";

다음 비트열의 범위는 현재 비트열을 5등분 한 것과 같다.

long sTemp = s + ((e - s + 1) / 5 * i);
long eTemp = s + ((e - s + 1) / 5 * (i + 1)) - 1;

그런데 우리는 구하고자하는 범위를 안다.

또한 0은 결국 0 -> 00000 -> 00000 00000 00000 00000 00000 -> ... 이 된다.

즉, 범위를 벗어나거나 0으로만 이루어진 비트열은 다음 연산에서 제외한다.

if (r < sTemp || l > eTemp || bitsTemp.equals("00000")) continue;

만약 범위안에 있으며 0으로만 이루어진 비트열이 아니면 다음 연산을 한다.

sum += countOnes(bitsTemp, sTemp, eTemp, l, r, n - 1);

정복할 때 1의 개수를 반환한다.

if (n == 0) {
    for (long i = s; i <= e; i++)
        if (l <= i && i <= r && bits.charAt((int) (i - s)) == '1') sum++;
}

n이 0이 되었다는 것은 현재 비트열이 최종 변환 비트열의 부분 비트열이라는 것이다.

해당 비트열에서 탐색 범위에 있는 1의 개수를 확인하여 반환한다.

이들을 한 번에 나타내면 다음과 같다.

public int countOnes(String bits, long s, long e, long l, long r, int n) {
    int sum = 0;
    if (n == 0) {
        for (long i = s; i <= e; i++)
            if (l <= i && i <= r && bits.charAt((int) (i - s)) == '1') sum++;
    } else for (int i = 0; i < 5; i++) {
        String bitsTemp = bits.charAt(i) == '1' ? "11011" : "00000";
        long sTemp = s + ((e - s + 1) / 5 * i);
        long eTemp = s + ((e - s + 1) / 5 * (i + 1)) - 1;
        if (r < sTemp || l > eTemp || bitsTemp.equals("00000")) continue;
        sum += countOnes(bitsTemp, sTemp, eTemp, l, r, n - 1);
    }
    return sum;
}

추가로 최초 비트열은 1인데 N은 1 이상이기 때문에 최초 비트열을 11011으로 N = N - 1로 한다.

쉬운 이해를 위해 n = 3, l = 36, r = 97 일 때의 예시를 그림으로 표현하면 다음과 같다.

📌 Code

GitHub Repository

class Solution {
    public int solution(int n, long l, long r) {
        return countOnes("11011", 1, (long) Math.pow(5, n), l, r, n - 1);
    }

    public int countOnes(String bits, long s, long e, long l, long r, int n) {
        int sum = 0;
        if (n == 0) {
            for (long i = s; i <= e; i++)
                if (l <= i && i <= r && bits.charAt((int) (i - s)) == '1') sum++;
        } else for (int i = 0; i < 5; i++) {
            String bitsTemp = bits.charAt(i) == '1' ? "11011" : "00000";
            long sTemp = s + ((e - s + 1) / 5 * i);
            long eTemp = s + ((e - s + 1) / 5 * (i + 1)) - 1;
            if (r < sTemp || l > eTemp || bitsTemp.equals("00000")) continue;
            sum += countOnes(bitsTemp, sTemp, eTemp, l, r, n - 1);
        }
        return sum;
    }
}