[programmers] lv.2 유사 칸토어 비트열

문제 바로가기

문제 접근

1. while문을 사용해서 주어진 규칙을 따라 n번만큼 반복 후 그 문자열에서 slicing으로 해당 범위 구한 후 count('1') >> 예상했지만 시간초과 발생
2. 마찬가지로 while문 사용하지만 주어진 범위의 길이가 천만으로 제한되어 있기 때문에 범위가 포함되는 부분적인 문자열만 구한 후 indexing

정답 코드

1 (시간초과)

def solution(n, l, r):
	while cnt != n:
    	x = x+x+y+x+x
        y = 5*y
        cnt += 1
    n_num = (x+x+y+x+x)[l-1:r]
    return blahblah~~  # 기억 잘 안남

2 (정답)

from math import ceil
def solution(n, l, r):
    x = '11011'
    y = '00000'
    tune = 0 # range를 새로운 문자열에 대해 tuning하기 위한 변수
    ranges = []
    now_num = '11011' # 11011부터 시작
    a,b = l,r
    for _ in range(n-1): # ranges를 정의 / for문 말고 list comprehension이용해도 됨.
        a = ceil(a/5)
        b = ceil(b/5)
        ranges.append([a,b])
    while len(ranges): # ranges가 존재하지 않을 때까지 반복
        new_l,new_r = ranges.pop() # 가장 작은 범주 대입
        new_l = new_l - 5*tune # 일부만 치환하기 때문에 그에 맞게 범주도 변화
        new_r = new_r - 5*tune
        num = now_num[new_l-1:new_r] # now_num에서 해당하는 문자열만 추출
        new = ''
        for i in num:
            if i == '1':
                new += x
            else:
                new += y
        now_num = new # 해당 문자열을 다시 1은 11011, 0은 00000으로 치환
        tune = 5*tune + new_l-1 # update tune
    fin_num = now_num[l-1-tune*5:r-tune*5]
    return fin_num.count('1')

math에서의 올림과 내림

from math import ceil # 올림
from math import floor # 내림