[프로그래머스] 억억단을 외우자

https://school.programmers.co.kr/learn/courses/30/lessons/138475

프로그래머스

 

분석

억억단에서 1 ~ 8이 등장하는 횟수는 다음과 같습니다.
1번 등장 : 1
2번 등장 : 2, 3, 5, 7
3번 등장 : 4
4번 등장 : 6, 8

1	2	3	4	5	6	7	8
2	4	6	8
3	6
4	8
5
6
7
8

➔ 8이 억억단에 등장하는 횟수는 1*8, 2*4, 4*2, 8*1 에 의해 등장할 수 있으므로 8의 약수의 개수인 4
➔ 숫자의 등장 횟수는 약수 개수와 동일

약수의 개수

0	1	2	3	4	5	6	7	8
1	1	1	1	2	1	3	1	3

뒤에서 부터 2개씩 비교하며 약수의 개수가 같거나 큰 수로 채우기

0	1	2	3	4	5	6	7	8
6	6	6	6	6	6	6	8	8

 

풀이

def solution(e, starts):

    # 약수의 개수
    arr = [1]*(e+1)
    for i in range(2, e+1):
        for j in range(i*2, e+1, i):
            arr[j]+=1
    
    answer = [0]*(e+1)
    answer[e]=e
    for i in reversed(range(0,e)):
        
        if arr[i] >= arr[answer[i+1]]:
            answer[i]=i
        else:
            answer[i] = answer[i+1]
        
    return [answer[i] for i in starts]