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

1. 첫 번째 접근

• 문제에 일정한 규칙이 있었기 때문에 해당 비트열을 실제로 만들고 직접 세는 문제는 아닐거라 생각했다. (비트열의 최대 크기가 5의 20승 95,367,431,640,625이라서 안될 것 같았다.)
• n-1번째에 1인 부분에 11011을 넣어서 만들어지는 모습이 재귀함수와 똑같다.

• 전체 1의 개수에서 범위 밖의 1의 개수를 빼주는 식으로 만들었다.

1. 시작부터 지정 구간까지 1의 개수를 구하는 재귀함수를 만든다.
   1-1. 재귀함수가 끝나는 조건을 설정한다.
   1-2. 비트열을 5^(n-1)로 나누어준다.(5등분)
   1-3. 나누었을 때 중간은 0으로 채워져 있기 때문에 3이상은 1을 빼준다.(5등분 하면 중간이 0이고 좌우대칭으로 [n-1비트열][n-1비트열][0...0][n-1비트열][n-1비트열] 형식이다.)
   1-4. 몫을 계산해 준다.
   1-5. 나머지를 계산해 준다.
   1-6. 몫과 나머지를 더해서 리턴한다.
2. 뒤에서 부터 지정구간까지 1의 개수를 구하는 재귀함수를 만든다.
   2-1. 1번과 동일하게 진행해 주는데 비트열이 좌우 대칭인 특징이 있어서 좌우를 반전시켜 준다.
   2-2. 좌우 반전을 했기 때문에 시작부터 지정 구간까지 1의 개수를 구하는 재귀함수를 사용해주면 된다.(사실, 1. 함수만 사용해도 된다. 가독성을 위해)
3. 전체 1의 개수에서 속하지 않은 1을 빼준다.

public int solution(int n, long l, long r)
{
	int answer = 0;
	long allOneCount = (long)Math.Pow(4, n);
	long front = GetFrontCount(n, l-1);
	long behind = GetBehindCount(n, r);
	answer = (int)(allOneCount -(front + behind));
	return answer;
}
private long GetFrontCount(int n, long l)
{
	if (n == 0)
		return 0;
	long eMinus = (long)Math.Pow(5, n - 1);
	long x = (int)(l / eMinus);
	if (x >= 3)
	{
		x -= 1;
	}
	long Quotient = (long)Math.Pow(4, n - 1) * x;
	long remainder = GetFrontCount(n - 1, l % eMinus);
	return Quotient + remainder;
}
// 중심을 기점으로 좌우가 동일해서 종료 인덱스인 r을 중심을 기점으로 반전한다.
private long GetBehindCount(int n, long r)
{
	if (n == 0)
		return 0;
	long eMinus = (long)Math.Pow(5, n - 1);
	r = (long)Math.Pow(5, n) - r;
	long x = (r / eMinus) ;
	if (x >= 3)
	{
		x -= 1;
	}
	long Quotient = (long)Math.Pow(4, n - 1) * x;
	long remainder = GetFrontCount(n - 1, r % eMinus);
	return Quotient + remainder;
}

• 결과 : 절반 맞고 절반 틀림
  실패!

2. 수정 사항

디버깅을 하다 보니 0이 중첩되는 구간을 1로 착각해서 계산하고 있었다.
1-5. 나머지를 계산해 준다. [n-1비트열][n-1비트열]0...0[n-1비트열][n-1비트열] 에서 [n-1비트열]은 [n-2비트열][n-2비트열]0...0[n-2비트열][n-2비트열]과 같이 생겼다.
1-추가. 나머지를 계산할 때 나머지가 0밖에 없는 중간부분이라면 계산하지 않는다.
1-6. 몫과 나머지를 더해서 리턴한다.

public int solution(int n, long l, long r)
{
	int answer = 0;
	long allOneCount = (long)Math.Pow(4, n);
	long front = GetFrontCount(n, l - 1);
	long behind = GetBehindCount(n, r);
	// 3. 전체 1의 개수에서 속하지 않은 1을 빼준다.
	answer = (int)(allOneCount - (front + behind));
	return answer;
}
// 1. 지정 구간까지 1의 개수를 구하는 함수를 만든다.
private long GetFrontCount(int n, long index)
{
	// 1-1. 재귀함수가 끝나는 조건을 설정한다.
	if (n == 0 || index == 0)
		return 0;
	long eMinus = (long)Math.Pow(5, n - 1);
	// 1-2. 비트열을 5^(n-1)로 나누어준다.(5등분)
	int x = (int)(index / eMinus);
	int y = x;
	// 1-3. 나누었을 때 중간은 0으로 채워져 있기 때문에 3이상은 1을 빼준다.
	if (y >= 3)
	{
		y -= 1;
	}
	// 1-4. 몫을 계산해 준다. 
	long Quotient = (long)Math.Pow(4, n - 1) * y;
	long remainder = 0;
	// 1-추가. 나머지를 계산할 때 나머지가 0밖에 없는 중간부분이라면 계산하지 않는다.
	if (x != 2)
	{
		// 1-5. 나머지를 계산해 준다. 
		remainder = GetFrontCount(n - 1, index % eMinus);
	}
	// 1-6. 몫과 나머지를 더해서 리턴한다.
	return Quotient + remainder;
}
// 2. 뒤에서 부터 지정구간까지 1의 개수를 구하는 재귀함수를 만든다.
private long GetBehindCount(int n, long index)
{
	if (n == 0)
		return 0;
	long eMinus = (long)Math.Pow(5, n - 1);
	// 2-1. 1번과 동일하게 진행해 주는데 비트열이 좌우 대칭인 특징이 있어서 좌우를 반전시켜 준다.
	index = (long)Math.Pow(5, n) - index;
	int x = (int)(index / eMinus);
	int y = x;
	if (y >= 3)
	{
		y -= 1;
	}
	long Quotient = (long)Math.Pow(4, n - 1) * y;
	long remainder = 0;
	if (x != 2)
	{
		// 2-2. 좌우 반전을 했기 때문에 시작부터 지정 구간까지 1의 개수를 구하는 재귀함수를 사용해주면 된다.
		remainder = GetFrontCount(n - 1, index % eMinus);
	}
	return Quotient + remainder;
}

3. 어려웠던 부분

• 재귀함수인 것은 알았지만 구조를 만드는 것이 어려웠다.
• 수학에서 칸토어 집합은 0과 1 사이의 실수로 이루어진 집합으로, [0, 1]부터 시작하여 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만들어집니다.
  이 문장을 이해하는데 시간을 한참 썼다. 문제를 풀고나서 이해가 됬다.