[프로그래머스] 유사 칸토어 비트열 (python)
문제 설명
Idea
풀이 방법이 직관적으로 떠오르지 않아 정의된 문제에 대한 규칙을 찾아보기로 했습니다.
1. 규칙 찾기
N=0 : 1 (1개)
N=1 : 1 / 1 / 0 / 1 / 1 (5개)
N=2 : 11011 / 11011 / 00000 / 11011 / 11011 (25개)
N=3 : 1101111011000001101111011 / 1101111011000001101111011 / 000000000000000000 / 1101111011000001101111011 / 1101111011000001101111011 (125개)
N-1 값들이 앞뒤*2로 생기며 중간은 N-1의 길이의 0이 생기는 규칙을 발견할 수 있습니다.
Ex. N=2라면, 11011(N=1)이 앞뒤*2로 생기며 중간에는 11011의 길이인 5개의 0이 생김
-> 11011 / 11011 / 00000 / 11011 / 110111
2. 규칙 정리
1. 규칙 찾기에서 찾은 규칙을 정리하면 아래와 같습니다. (1만 세서 정리)
N cantor_bit total_1 len
1 1/1/0/1/1 4 5
2 4/4/0/4/4 16 25
3 16/16/0/16/16 64 125
4 64/64/0/64/64 256 625
5 256/256/0/256/256 1024 3125
N이 증가함에 따라 1의 수는 $4^{N}$으로, 길이는 $5^{N}$으로 증가하는 규칙을 발견할 수 있습니다.
Ex. N=2라면, 1의 수는 총 16개 (4 / 4 / 0 / 4 / 4), 유사 칸토어 길이는 25
3. 수식 정리
1. 총 5개의 그룹으로 나눔 (X / X / 0 / X / X 구조로 정리되기 때문, 2. 규칙 정리 참고)
2. L, R의 값을 기준으로 해당 값이 5개의 그룹 중 어디에 속하는지 판단
3. 0 ~ G-1 그룹에 해당하는 비트열 수를 더함 (2번 그룹은 비트열 수를 더하지 않음, 0이 나오는 구간)
4. G 그룹을 1번부터 다시 계산 (G그룹은 N-1 그룹으로 변경되어, 이를 반복 계산)
Ex.
N=3이고 R=125(1-base)라면, 16 / 16 / 0 / 16 / 16에서 125에 해당하는 마지막 16 그룹을 제외한 1을 카운트 (48, 16*3)
마지막 16 그룹을 다시 나눠 4 / 4 / 0 / 4 / 4로 분할(N-1 그룹), 이 때 R은 125 -> 25로 변경하여 25에 해당하는 마지막 4 그룹을 제외한 1을 카운트 (60, 48 + 4*3)
마지막 4 그룹은 더 이상 나눌 필요가 없음 (1 / 1 / 0 / 1 / 1 로 나눠 계산하는건 의미X), R은 25 -> 5로 변경하여 1 카운트 (64, 60 + 4)※ 유의사항
o L~R 사이 칸토어 비트열 1 개수 계산 시, (0~R 1의 개수) - (0~L-1 1의 개수)로 계산이 더 편함
o L~R을 한번에 구하려고 하면 고려해야하는 예외 상황이 복잡 (L과 R이 같은 그룹인 경우 등)
Solution
def solution(n, l, r):
def cnt_cantor(N, remainder):
plus = [0, 1, 2, 2, 3]
cnt = 0
while N > 1:
bit = 4**N // 4
length = 5**(N-1)
quotient, remainder = divmod(remainder, length)
# q=2면 00000 구간이라서 -1로 해당 카운트 제외
cnt += bit * quotient if quotient <= 2 else bit * (quotient-1)
N -= 1
# 00000 구간인 경우이면 그 이후 계산X
if quotient == 2:
break
else:
cnt += plus[remainder]
return cnt
if n == 1:
return "11011"[l-1:r].count("1")
L = cnt_cantor(n, l-1)
R = cnt_cantor(n, r)
return R - L
칸토어 비트열은 N에 따라 1의 개수는 $4^{N}$, 길이는 $5^{N}$의 규칙을 가집니다.
주어진 N에 대해서 $4^{N}$과 $5^{N}$의 값을 구해준 뒤 주어진 값의 그룹을 찾습니다. (quotient)
주어진 값에 해당하는 그룹을 제외한 그룹의 1의 개수를 카운트하고 선택한 그룹을 다시 분할합니다.
마지막 4 / 4 / 0 / 4 / 4에서 선택된 그룹을 다시 1 / 1 / 0 / 1 / 1로 분할하여 계산하지 않고 plus[remainder]에 접근하여 1의 개수를 더해줍니다.
Refactoring
import math
def solution(n, l, r):
# 5^n 전체 범위에 대한 1의 개수 : 4^n
def sol(x):
if x <= 2:
return x
elif x <= 5:
return x - 1
base = int(math.log(x) // math.log(5))
bit = 4 ** base
length = 5 ** base
quotient = x // length
remainder = x % length
ans = bit * quotient if quotient <= 2 else bit * (quotient-1)
if quotient == 2:
return ans
return ans + sol(remainder)
L = sol(l - 1)
R = sol(r)
return R - L
접근 방법은 Solution과 동일합니다.
다만, 주어진 값과 5을 나눠 해당 값의 위치를 곧바로 찾아냅니다. (log(x) // log(5))
기존은 N=20, R=100이라면 N=20,19,18...2가 되면서 100에 해당하는 1의 개수를 카운트합니다.
log(100)//log(5)로 100 값이 위치한 N=2인 곳을 찾아내서 N=2에 해당하는 비트열의 개수를 카운트합니다.
해당 접근법은 N의 수와 상관없이 주어진 값 X에 해당하는 비트열을 바로 접근할 수 있는 장점이 있습니다.
댓글
댓글 쓰기