프로그래머스는 풀이한 문제에 대해 타인의 코드를 참조할 수 있도록 지원한다. 커뮤니티 추천 풀이에 비해 내 풀이의 성능이 나았기 때문에 글을 작성하게 되었다. 커뮤니티 최고 추천 풀이는 다음과 같다.
def solution(n, l, r):
answer = r-l+1
for num in range(l-1,r):
while num>=1:
a,b=divmod(num,5)
if b==2 or a==2:
answer-=1
break
num=a
return answer하지만 위의 코드는 기본적으로 n의 크기가 커짐에 따라 r - l 값에 비례하여 시간 복잡도가 상승한다. 왜냐하면 최댓값부터 시작하여 소거법을 기반으로 모든 칸토어 비트열을 순회하기 때문이다.
n과r - l이 큰 테스트에서는 시간 복잡도가 상승한다.
이러한 로직을 개선하려면 칸토얼 비트열이 프렉탈의 성질을 가지고 있음을 활용하면 된다. 코드는 다음과 같다.
def solution(n, l, r):
if n == 1:
return sum([1, 1, 0, 1, 1][l - 1: r])
block_size = 5 ** (n - 1)
block_n_start = (l - 1) // block_size + 1
block_n_end = (r - 1) // block_size + 1
block_idx_start = (l - 1) % block_size + 1
block_idx_end = (r - 1) % block_size + 1
res = 0
for block_n in range(block_n_start, block_n_end + 1):
if block_n != 3:
if block_n_start == block_n_end:
res += solution(n - 1, block_idx_start, block_idx_end)
elif block_n == block_n_start:
res += solution(n - 1, block_idx_start, block_size)
elif block_n == block_n_end:
res += solution(n - 1, 1, block_idx_end)
else:
res += 4 ** (n - 1)
return res
모든 n에 대해 비트열을 5개로 구분하고, 각각을 block이라 정의했다. 가운데 블록은 모든 값이 0이 되고, 나머지 블록은 n-1 칸토어 비트열과 동일한 형태를 갖는다. 따라서 재귀적인 성질을 활용하면 된다.
단, 예외가 되는 지점만 별도로 계산하면 된다. 함수 solution을 통해 최초로 전달되는 매개변수는 처음과 끝에 대한 인덱스 정보를 포함한다. 따라서 부분합이 이루어지는 지점은 처음과 끝에만 존재한다. 물론 처음과 끝이 동일한 블록에 존재하는 경우도 존재할 수 있다.
위와 같은 코드를 사용하면 예외적으로 처리되는 처음과 끝만 재귀적으로 처리된다. 즉, 기존 O(5^n) 복잡도를 O(n)으로 개선한 것이다.
