문제링크
https://school.programmers.co.kr/learn/courses/30/lessons/148652#
접근
비트열의 길이는 l,r의 크기에서 찾아볼 수 있다 (5^n)
n은 20 이하의 수이고, 5^20은 조 단위의 수 이므로 O(N)보다 좋은 풀이를 생각해야하고, O(logn)의 복잡도를 가지는 알고리즘으로 풀어야겠다고 생각했다.
그리고 n에 따른 비트열이 일정한 규칙을 가지고있으므로 분할정복으로 풀 수 있을 것이라 생각했다.
풀이
n에 대해서, 구간 [l,r]에서의 1의 개수를 구하는 문제이다.
함수 f(n,k)는 n에 해당하는 비트열에 대해 k번째 수까지의 1의 개수라고 정의하였다.
f(n,k) = n비트열에서 k번째 수까지의 1의 개수
따라서 우리가 구하고자 하는 구간에서의 1의 개수는
f(n,r) - f(n,l-1)로 표현할 수 있다.
def solution(n, l, r):
return f(n,r) - f(n,l-1)그렇다면 이제 함수 f(n,k)를 만들어보자.
비트열을 치환하는 규칙에 의해 비트열의 길이는 5^n이 되고, 1의 총 개수는 4^n이다.
n==1 -> 11011 (길이 5, 1 총 4개)
n==2 -> 11011 11011 00000 11011 11011 (길이 25, 1 총 16개)
n==3 -> n==2짜리 비트열 / n==2짜리 비트열 / 00000 5개/ n==2짜리 비트열/ n==2짜리 비트열
(길이 125, 1 총 64개, n==2짜리 비트열은 16개의 1을 가지므로)
...
이와 같은 규칙이 반복되므로 n비트열을 항상 5개의 구역(0,1,2,3,4)으로 나누고 해당 구역에 대해서 재귀적으로 f를 호출하도록 구성하였다.
예를 들어 n==2, k==17인 경우, 비트열은 11011 11011 00000 11011 11011이고 17번째 비트는 구역 3에 존재하게 된다. 따라서 구역 2까지의 1의 개수와 구역 3에서의 1의 개수의 합을 구하면 되는 것이다. 이를 식으로 표현하면 다음과 같다.
k의 구역을loc이라고 하자
f(n,k) = (loc-1 까지의 1의 개수) + f(n-1, k-(loc 전까지 비트수))
알고리즘은 이렇게 끝이 났고, 예외적인 경우만 처리하면 된다.
먼저 k가 5의 배수면 loc이 생각한대로 나오지 않으므로 (k==10이면 구역 1이어야 하는데 구역 2가 됨) 이 경우에 loc을 1 낮춘다.
div = 5**(n-1) # 나눌 수 (현재 n보다 하나 작은거로 나눠서, 항상 5개의 구역으로 나눌 수 있도록 함)
mul = 4**(n-1) # 1의 개수
loc = k//div # 5개로 나눴을 때 위치 0 1 2 3 4
if k%div==0: # 딱 5로 나누어떨어졌을 때
loc-=1또한 n비트열에서 가운데 구역은 0으로 되어있는 부분이 있는데, 해당 부분에서는 1이 존재하지 않으므로 (loc-1 까지의 1의 개수)만 구하면 되는 것이다.
if loc <2: # 11<- 011
return mul*loc + f(n-1,k- loc*div)
elif loc == 2: # 0 part
return mul*loc
else: # 110 11<-
return mul*(loc-1) + f(n-1,k- loc*div) mul * loc을 하면 현재loc이전까지의 1들을 구할 수 있다.- 0이 끼는 부분때문에
loc이 3또는 4일때loc-1을 해줘야 한다 - 현재
loc==2면 00000 이런 부분에 있다는 것이므로, 굳이 더 들어가서 1의 개수를 확인 할 필요가 없다. 어차피 0이다.
마지막으로 n==1인 경우 재귀함수를 탈출할 조건을 만들어야 한다. 11011에서 k에 해당하는 수의 1의 개수를 반환하면 된다.
if n==1:
return k if k<=2 else k-1정답코드
def f(n,k):
if n==1:
return k if k<=2 else k-1
div = 5**(n-1) # 나눌 수 (현재 n보다 하나 작은거로 나눠서, 항상 5개의 구역으로 나눌 수 있도록 함)
mul = 4**(n-1) # 1의 개수
loc = k//div # 5개로 나눴을 때 위치 0 1 2 3 4
if k%div==0: # 딱 5로 나누어떨어졌을 때
loc-=1
if loc <2: # 11<- 011
return mul*loc + f(n-1,k- loc*div)
elif loc == 2: # 0 part
return mul*loc
else: # 110 11<-
return mul*(loc-1) + f(n-1,k- loc*div)
def solution(n, l, r):
return f(n,r) - f(n,l-1)
