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

 

문제 설명

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

 

 

입출력 예 설명

2 번째 유사 칸토어 비트열은 "1101111011000001101111011" 입니다. 음영 표시된 부분은 폐구간 [4, 17] 이며 구간 내의 1은 8개 있습니다.

 

출처

https://school.programmers.co.kr/learn/courses/30/lessons/148652?language=java

프로그래머스

 

 

---

 

첫 번째 시도 

• 문제자체의 이해가 어려워 빠르게 읽고 예제를 읽었다. 
  • 규칙이 눈에 보여 문제 풀이에 집중했지만 우선으로 중요한건 문제의 목표를 꼼꼼히 읽지 않았다.
  • 그래서 결국 해설을 보는데에도 시간이 많이 걸렸다.
• 또한 비트열을 하나하나 구해야하하나 생각이 들었다. 
  • 하지만 비트열 길이는 5배씩 증가하기 때문에 시간 복잡도는 물론 공간복잡도까지 초과하였다. 
• 결국 고민하다 못풀었다. 

 

 

해설

목표

• n번째 비트열에서 구간 l ~ r 까지 1의 개수를 구하는 것 
• = n번째 비트열에서 (r 까지의 1의 개수) - (l-1까지의 1의 개수) 와 동일하다. 

 

규칙 파악

• 예제를 기반으로 비트열을 적어보면 다음과 같다. 
• 또한 적다보면 n 번째 비트열과 n-1 번째 비트열간에 규칙을 알 수 있다. 

 

n번째와 n-1 번쨰의 관계 

• n-1 번째에서 비트가 0 또는 1 에 따라 n번째 결과가 정해진다. 
• f(n) = n번째 비트열' 라고 하면 
• f(n) = f(n-1)f(n-1) 00...0 f(n-1)f(n-1) = f(n-1)f(n-1) 0구간 f(n-1)f(n-1)  규칙을 알 수 있다. 

1개수 구하기

우선 n 번째에서 r의 구간을 구한다. 

구간을 색처럼 5가지로 나눌 수 있다.

이제 다시 2가지로 나눠서 l까지의 1개수를 셀 수 있다.

 

1. r 이전 구간의 1 개수 구하기 (핑크, 노랑, 그린!) 

• r=17 파란 구간 이전에 3가지 구간에 대한 1 개수를 구할 수 있다. 
• 각 핑크, 노랑 구간은 n-1 번째 비트열의 1 개수와 동일하다. (n번째에서 5배 증가했고, 구간을 5개로 나누었기 때문) 
• 따라서 구간이 1이라면, (현재 구간 -1) x (n-1 번째 비트열의 1의 개수)를 곱하면 된다. 
• 구간이 2라면, 현재 구간 x (n-1 번째 비트열의 1의 개수)를 구하면 된다.
• 구간이 3 또는 4라면, (현재 구간 - 1) x (n-1 번째 비트열의 1의 개수)를 구하면 된다.

2. r이 속한 구간의 1개수 구하기 

• 2번째 비트열에서 파란색 구간에서 r 위치를 구해야 한다. 
• = 1번째 비트열에서 r - (r 앞 구역 개수 *  5^(n-1)) 까지의 1개수와 동일한다.
• 재귀적으로 0번째 비트열이 나올때까지 1 개수를 세면 된다. 

 

 

 

 
public class Programmers148652 {
    public static void main(String[] args) {
 
        Solution solution = new Solution();
        System.out.println(solution.ss(1, 2, 3));
    }
}
 
class Solution {
    public int ss(int n, long l, long r) {
        return (int)(count(n, r) - count(n, l-1));
    }
 
    // n 번째 비트열에서 k까지 1의 개수
    private long count(int n, long k) {
        if (n == 0) {
            return 1;
        }
 
        long preBitStringNumber = n - 1;
        long divisor = (long) Math.pow(5, preBitStringNumber);
        long numberOfOne = (long) Math.pow(4, preBitStringNumber);
 
        long zone = (int) (k / divisor);
        if((k % divisor) == 0) zone--;
 
        if (zone == 2) {
            // 0만 있는 구역
            return numberOfOne * zone;
        } else if (zone < 2) {
            // 0 이전 구역
            return numberOfOne * zone + count(n - 1, k - (divisor * zone));
        } else {
            return numberOfOne * (zone - 1) + count(n - 1, k - (divisor * zone));
        }
    }
}

 

 

참고

https://dico.me/back-end/articles/370/ko