Welcome to My IT World

코딩테스트 연습 - 유사 칸토어 비트열

문제요약

칸토어 집합이란, [0,1] 부터 시작해서 각 구간을 3등분 한 후에 가운데 구간을 반복적으로 제외하는 방식

다음과 같이 유사칸토어 비트열을 생성함

• 0 번째 유사칸토어 비트열 : 1
• n 번째 유사칸토어 비트열 : n-1 번째 비트열에서 1을 ‘11011’로 치환하고 0을 ‘00000’로 치환

n 번째 유사칸토어 비트열에서 특정 구간 내의 1의 개수가 몇개인지 return하라

입력

1≤ n ≤ 20

1≤ l, r ≤ 5^n

• l ≤ r < l + 10^7
• ㅣ과 r은 비트열에서 인덱스(1-base)이며, 폐구간 [l, r]을 나타냄

출력

return int

어떻게 풀까?

• 주의할 점 : l, r 이 1로 시작하는 인덱스이며 l과 r을 포함하는 구간으로 구해야 함
• 1≤ l, r ≤ 5^n 및 l ≤ r < l + 10^7 조건으로 인하여, 시간복잡도를 고려한 알고리즘 구현 필요
• 칸토어 집합 자체가 규칙이 있음 ⇒ 손으로 풀어보며 규칙을 찾아보자

⇒ 길이에 따라서 일정한 유사성을 가진 비트열이 생성되고 길이에 따라서 4의 배수로 1의 개수를 구할 수 있음

⇒ r-1번(index-0)까지의 1의 개수에서 l-2번(index-0)까지 1의 개수를 제외해주면 될 것

⇒ 이 때, 1의 개수는 해당 길이를 통해서 n번째 비트열에 속하는 지를 구한 후에 n-1번째 비트열의 길이로 그룹을 구하고 그 그룹의 개수만큼 4의 n-1승을 활용하여 구하면 됨

(단, 그룹의 수가 3개 이상일 때는 0이 5^(n-1)개 있는 그룹이 3번째 구간에 있으므로 그만큼을 제외해주어야함)

나머지의 경우, 재귀를 활용하여 처리

⇒ 현재, n을 5로 나누어주는 것으로 계속 진행을 하고 있기 때문에, 재귀의 종료조건은 n이 5이하가 될 때로 설정

(이 때는, '11011’[:길이]에서의 1의 개수를 반환하면 될 것)

내 코드

def get_power_of_base5(num):
	power = 1
	while 5**(power+1) < num:
	power += 1
	return power

def get_1_cnt(num):
	res = 0
	
	if num <= 5:
	    return '11011'[:num].count('1')
	
	power = get_power_of_base5(num)
	
	group = num // (5 ** power)
	
	res += group*(4** power)
	
	if group == 2:
	    return res
	elif group >= 3:
	    res -= 4 ** power
	
	remain = num % (5 ** power)
	if remain:
	    return res + get_1_cnt(remain)
	
	return res

def solution(n, l, r):
	return get_1_cnt(r) - get_1_cnt(l-1)

어려웠던 점

• 처음에 시간복잡도를 미처 고려하지 못한 탓에 아래와 같은 코드를 작성하였고 시간초과 오류가 발생하였다.

def solution(n, l, r):
    ans = 0

    r -=1
    l -=1

    memo = []
    memo.append('1')
    for i in range(1, n+1):
        memo.append(memo[i-1]*2+'0'*5**(i-1)+memo[i-1]*2)

    r_group = (r//5**(n-1))

    if r_group <= 2 :
        ans += r_group*(4**(n-1))
    else:
        ans += (r_group-1)*(4**(n-1))

    for i in range(r_group*(5**(n-1)), r+1):
        if memo[n][i] == '1':
            ans += 1

    l_group = ((l//5**(n-1)))
    if l_group <= 2:
        ans -= l_group*(4**(n-1))
    else:
        ans -= (l_group-1)*(4**(n-1))

    for i in range(l_group*(5**(n-1)), l):
        if memo[n][i] == '1':
            ans -= 1

    return ans

• 답을 찾는 데, n번째라는 인자값은 굳이 필요하지 않았다. 오히려 이 n번째 인자값을 어떻게 사용할지 고민하는 과정이 혼란을 주었던 것 같다. 주어지는 모든 인자들이 문제 해결에 필요하지 않을 수 있다는 점을 명심하자.
• 재귀함수를 사용할 때, num이 1이 되는 조건을 처음에 걸었었는데 함수 내부에서 num을 5로 나누어 진행을 하다보니 이 조건으로 인하여 무한재귀가 발생하였다. 인자값을 어떻게 처리하는 지 잘 확인하고 해당 처리를 거치지 못하는 값에 대해서 종료조건이나 예외처리를 해주어야할 것이다.
• 처음에 group 개수에 대한 1의 개수를 res에 반영함에 있어서 아래와 같이 처리하여 group이 1개이고 나머지가 있을 때를 제대로 처리하지 못했다.

def get_1_cnt(num):
...(중략)...

if group <= 2:
    return group*(4** power)
elif group >= 3:
    res -= 4 ** power
if remain:
        return res + get_1_cnt(remain)
return res

• 전체적으로 처리를 한 후에, 일부 예외사항을 반영하는 아래와 같은 방식으로 변경하였다.

def get_1_cnt(num):
...(중략)...

res += group*(4** power)

if group == 2:
    return res
elif group >= 3:
    res -= 4 ** power

if remain:
        return res + get_1_cnt(remain)
return res