프로그래머스 - 유사 칸토어 비트열 (Java)

 

문제 개요

 

수학에서 칸토어 집합은 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]을 나타냅니다.

 

입출력 예시

 

---

 

풀이

 

문제를 풀기 위해 실제로 비트열 변환을 시키기 위해 배열 or 리스트 or 문자열을 사용해 볼까?라는 생각을 해볼 수 있을 것 같다.

 

그런데 1, 0이 각각 11011, 00000로, 비트 변환이 일어나면 문자열 혹은 배열의 크기가 다섯 배로 늘어야 한다. 일반적인 경우라면 배열 혹은 리스트로 만들거나 String 형태로 이어 붙여서 간단하게 끝낼 수도 있겠지만 이 경우에는 비트열 변환을 n번 진행한다고 했을 때, 총 배열 or 리스트 or String 크기(길이)가 5^n개가 된다는 것이다.

 

제약 조건을 고려했을 때 발생 가능한 총크기가 5^20(5의 20승) 개이기에 int 자료형보다 큰 long을 사용해야 한다. 그런데 배열, 리스트의 인덱스의 최대 크기는 int형의 크기이고, String으로 푼다 해도 내부 메소드을 사용하기 위해서는 int형 매개변수를 넣어줘야 하기에 문제를 풀기 위해서는 동적으로 특정 구간의 1의 개수를 구하는 방식으로 접근해야 한다.

 

문제에서 원하는 바는 특정 구간에 존재하는 1의 갯수를 구하는 것이기 때문에 그에 초점을 맞춰 아래처럼 생각해 봤다.

• 1 -> 11011로 바뀌기 때문에 1을 변환해야 한다면, 1개에서 4개로 바뀐다. 즉, 4배가 된다.
• n=2를 진행할 때, 11011 -> 11011 11011 00000 11011 11011 이 된다.

 

위의 두 가지 사실을 토대로 생각했을 때 n=1을 실행한 결과 값이 11011이라는 걸 감안하여 다시 작성해 본다면, n이 1인 경우를 f(1)이라고 표현했을 때, n=2 즉 f(2) = f(1) f(1) 00000 f(1) f(1)이라는 결과를 얻을 수 있다.

 

그렇다면, f(3)은 아래와 같이 표현될 수 있을 것이다.

11011 11011 00000 11011 11011
11011 11011 00000 11011 11011
00000 00000 00000 00000 00000 
11011 11011 00000 11011 11011
11011 11011 00000 11011 11011

 

이를 아까와 같이 f(3)으로 표현한다면 f(3) = f(2) f(2) 0x25 f(2) f(2) 이렇게 표현이 가능하다.

 

이를 반복했을 때 f(n)은 결국 f(n-1) f(n-1) 0x5^n f(n-1) f(n-1)과 같이 표현될 수 있고, 이렇게까지 유추가 되었다면 우리가 알아낸 사실은 다음과 같다.

1. 변환을 수행할 때마다 전체 1의 개수는 4배가 된다.
2. f(n) = f(n-1) f(n-1) 0x5^n f(n-1) f(n-1)이다.

 

문제에서 원하는 것은 특정 구간인 l 번째부터 r 번째까지 1의 개수인데, 이는 (처음부터 r 번째까지 1의 개수) - (처음부터 l - 1 번째 까지)의 결과와 같다.

 

처음부터 l부터 r번째 비트 사이의 1의 개수를 구하는 것은 다소 복잡하게 느껴질 수 있지만, 처음부터 특정 자릿수까지 1의 갯수는 구할 수 있다. (물론 l부터 r번째 비트를 한번에 구하는 방법도 존재하고, 간단할 수 있지만, 나는 위에 말한 방법대로 풀었다.)

 

처음부터 k 번째까지의 비트열 중 1의 갯수를 구하는 방법은 다음과 같다.

1. 5^0, 5^1,,, 5^n까지 순회하면서 k 보다 커지기 직전까지 탐색한다. (여기서는 k보다 커지기 직전의 5의 지수를 a라고 하겠다)
2. 여기서 구한 5^a라는 수가 사실 f(a)를 수행했을 때의 1의 개수와 같다.
3. 예를 들어 k = 52라고 했을 때, a는 2가 되고, 5^a는 25가 된다.
4. 우리는 0부터 52번째까지 1의 개수를 구해야 하고, 5^a의 두 배를 했을 때 0부터 50번째까지 1의 개수를 구할 수 있다.
   • 여기서 코드로 표현하기 위해 수식으로 만드는 것은 k에서 5^a를 나누는 작업을 실시한 것을 표현한 것과 같다.
   • 52(k) = 5^2(a) x 2 + 2
5. 그럼 51과 52의 2개의 나머지가 남는데, 여기서 다시 한번 되새기자면, f(3) = f(2) f(2) 0x5^2 f(2) f(2)이다.
6. 즉, 51과 52번째 비트는 무조건 0이 된다는 뜻이고, 앞으로도 k / f(a)를 실시해서 몫과 나머지를 구할 때 f(a) f(a)에 포함된 1의 갯수와 f(a)f(a) 0x5^a는 같다는 것을 의미한다.
7. 따라서 몫이 2인 경우에는 나머지가 존재하더라도 그대로 계산을 종료할 수 있는 것이다.
8. 하지만 이 외로 몫이 2가 아닌 경우에는 나머지를 k로 두고 다시 위 작업을 반복하면 된다.

 

---

 

코드

 

import java.util.*;

class Solution {
    public int solution(int n, long l, long r) {
        return countOne(n, r) - countOne(n, l-1);
    }
    
    public int countOne(int n, long target) {
        int answer = 0;
        int exCount = 0;
        long section = 1;
        for (int i=0 ; i<n-1 ; i++) {
            exCount++;
            section *= 5;
        }

        while (section > 0) {
            long mok = target / section;
            long nmg = target % section;
            if (mok == 0) {

            } else if (mok == 1) {
                answer += Math.pow(4, exCount) * mok;
                target = nmg;
            } else if (mok == 2) {
                answer += Math.pow(4, exCount) * mok;
                target = 0;
            } else {
                answer += Math.pow(4, exCount) * (mok-1);
                target = nmg;
            }
            section /= 5;
            exCount--;
        }
        return answer;
    }
}

 

---

 

제출 결과

 

제출 결과

 

문제를 프로그래머스 사이트에서 풀다가 단축키가 너무 고파서 인텔리제이 IDE를 사용하여 코드를 작성하고 프로그래머스 사이트에 옮겨 넣었다.

 

내가 IDE에 작성한 코드는 깃허브(여기 링크)에 올려두었다.