[프로그래머스 Level.2] 유사 칸토어 비트열 (연습문제) (Java)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/148652

프로그래머스

 

 

 

 

코딩테스트 연습 > 연습문제 > 유사 칸토어 비트열

 

 

 

문제 설명

 

 

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

 

---

 

입출력 예

n	l	r	result
2	4	17	8

 

---

입출력 예 설명

 

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

 

 

 

 

나의 코드

// n>=1 일 때, f(n) = f(n-1) f(n-1) 0...0 f(n-1) f(n-1)
// 이렇게 5개 구역으로 나누어지므로 주어진 수를 5^(n-1)으로 나누면 0, 1, 2, 3, 4 총 5개 구역 중에 해당 위치의 구역이 정해짐
class Solution {
    public int solution(int n, long l, long r) {
        int answer = 0;
        
        long cntR = getOneCount(n, r, 0);
        long cntPrevL = getOneCount(n, l-1, 0);
        
        answer = (int) (cntR - cntPrevL);
        
        return answer;
    }
    
    public long getOneCount(int n, long target, long sum) {
        if(n == 1) {
            if(target <= 2)
                return sum + target;
            else
                return sum + target - 1;
        }
        
        long q = target / (long) (Math.pow(5, n-1));
        long r = target % (long) (Math.pow(5, n-1));
        
        if(q <= 2)
            sum += (long) (Math.pow(4, n-1)) * q;
        else
            sum += (long) (Math.pow(4, n-1)) * (q-1);
        
        if(q == 2 || r == 0) return sum; 
        
        return getOneCount(n-1, r, sum);
    }
}

 

풀이

1. 몇 개의 유사 칸토어 비트열을 만들어 보자. 
   n=0 일 때, f(0) = 1, length(0) = 1 = 5^0, countOne(0) = 1 = 4^0
   n=1 일 때, f(1) = 11011, length(1) = 5 = 5^1, countOne(1) = 4 = 4^1
   n=2 일 때, f(2) = 11011 11011 00000 11011 11011, length(1) = 25 = 5^2, countOne(2) = 16 = 4^2
   .....
2. 다음과 같이 몇 개의 유사 칸토어 비트열을 만들어 보면 다음의 규칙을 찾을 수 있다.
   n>=1 일 때, f(n) = f(n-1) f(n-1) 0...0 f(n-1) f(n-1) 이고 총 길이는 5^n 이고 1의 개수는 4^n 이다.
3. 이렇게 f(n)은 총 5개 구역으로 나누어지므로 주어진 target의 위치를 찾기 위해서 target을 5^(n-1)로 나누면 target이 있는 구역을 찾을 수 있다.
4. f(n)에서 target이 있는 구역을 찾으면 f(n-1)의 1의 개수는 4^(n-1) 을 이용하여 해당 구역 전에 있는 구역들의 1의 개수를 더한 후에 해당 구역에서 target의 위치까지만큼 1의 개수를 더해주면 된다.
5. 따라서 처음부터 target 위치까지의 1의 개수를 구하는 것이므로 l부터 r까지의 1의 개수를 구하기 위해서는 r까지의 1의 개수에서 (l - 1)까지의 1의 개수를 구해서 빼주면 된다.
6. 그럼 f(n)에서 target의 위치까지 1의 개수를 구하는 getOneCount(n, target, sum)를 보자.
7. target이 있는 구역을 찾기 위해 taget을 5^(n-1)로 나눈 몫을 구해 q에 저장한다.
8. 그리고 target의 위치를 찾기 위해 target을 5%(n-1)로 나눈 나머지를 구해 r에 저장한다.
9. q=0,1,3,4 일 때 f(n-1) 구역이고 q=2일 때 0...0 구역이므로 q가 2 이하이면 q의 바로 전 구역까지 1의 개수는 4^(n-1) * q이고 q가 3 이상이면  q의 바로 전 구역까지 1의 개수는 4^(n-1) * (q-1) 이다. (q = 2구역엔 1이 없기 때문)
10. 이렇게 target이 있는 구역의 바로 전 구역까지 1의 개수를 구해 sum에 더해준 다음 target이 있는 구역에서 target의 위치까지의 1의 개수를 구하면 된다.
11. 만약 q가 2이면 target의 위치는 0...0의 구역이므로 1이 없으므로 더 이상 구할 필요가 없다. 또한, r이 0인 경우에도 taget을 5^(n-1)로 나누어 딱 떨어졌다는 것으로 target의 위치가 q에 해당하는 구역의 끝이라는 뜻이므로 더 이상 구할 필요가 없다.
12. 그게 아니라면  q의 f(n-1) 구역에서 r의 위치를 찾는 것이므로 getOneCount(n-1, r, sum)으로 재귀 호출을 해서 n이 1이 될 때까지 계속 sum에 1의 개수를 더해주다가 n이 1이 되면 이 경우만 처리해주고 끝내면 된다.
13. n이 1일 때는 f(n) = 11011 이므로 마찬가지로 해당 target의 위치까지 1의 개수를 더해주면 된다. target은 index가 아닌 몇 번째를 의미하므로 target이 2 이하라면 target을 더해주고 3 이상이라면 target - 1을 더해주면 된다.
14. 이렇게 target까지의 1의 개수를 구할 수 있으므로 target이 r일 때를 구하고 target이 l-1일 때를 구하고 빼서 l부터 r까지의 1의 개수를 구한 후 반환한다.

 

참고 : https://blog.naver.com/chochita0311/222973468515