[프로그래머스][약수,배수][DP] 억억단을 외우자

억억단을 외우자

프로그래머스

 

• 내 풀이
  • e 이하의 숫자만 확인하므로 두 수를 곱해서 e 가 될만큼만 2중for문 돌면서 갯수 세기
  • 1~e 부터 e까지의 범위중에 나올 수 있는 갯수가 최대인 값을 cnt에 미리 모아두기
    
    • 최대인값k가 나오면 k+1이후 범위 탐색
  • bisect으로 cnt에서 start가 들어갈 위치 찾아서 해당 값 넣기

from bisect import bisect_left
def solution(e, starts):
    answer = []
    nums=[0 for _ in range(e+1)]
    for i in range(1,(e+1)//2):
        for j in range(i,(e//i)+1):
            if i==j:
                nums[i*j]+=1
            else:
                nums[i*j]+=2
    
    last=1
    cnt=[]
    while last<=e:
        k=last+nums[last:e+1].index(max(nums[last:e+1]))
        cnt.append(k)
        last=k+1
        
    for start in starts:
        idx=bisect_left(cnt,start)
        answer.append(cnt[idx])
    
    return answer

 

• 다른 사람 풀이 - fail(과정은 맞는거같은데 시간초과남)
  • 어떤 숫자 num 이 억억단에서 등장한 횟수는 num의 약수의 갯수와 같다

# 약수 구하는 풀이- 알아두기
# cnt[i]는 i의 약수 개수
cnt = [1] * (e + 1)

for i in range(1, e + 1):
    for j in range(i * 2, e + 1, i):  # i의 배수에 대해
        cnt[j] += 1  # i는 j의 약수이므로 증가

 

풀이 참고 링크

1. 약수의 개수 구하기 - 방법 2, O(eloge) with 조화수열

1부터 e까지의 숫자 num에 대해, num*2, num*3, num*4, ...를 e까지 진행하여
num*k에 해당하는 count를 1씩 더해주는 방법

1*1, 1*2, 1*3, 1*4 ... 1*500만
2*1, 2*2, 2*3, 2*4 ... 2*250만
3*1, 3*2, 3*3, 3*4 ... 3*167만
...
10000*1, 10000*2, 10000*3, 10000*4 ... 10000*500
...
500만*1
⇒ 시간복잡도: 조화수열에 근사한 O(eloge)


2. 구간 내 최댓값 구하기
e가 고정되어 있다는 점을 활용하여 뒤에서부터 접근하는 dp를 사용

• 약수 개수 구하기
  • cnt 배열을 사용하여 각 숫자의 약수 개수를 저장
  • 특정 숫자 nnn의 배수는 모두 nnn을 약수로 가지므로, nnn의 배수마다 약수 개수를 1씩 증가
• DP 배열 생성
  • dp[n]은 구간 [n,e]에서 약수의 개수가 가장 많은 수
  • 뒤에서부터 거꾸로 탐색하면서, 현재 숫자와 다음 숫자 중 약수 개수가 많은 쪽을 선택

def solution(e, starts):
    # cnt[i]: i의 약수 개수
    cnt = [1] * (e + 1)
    
    for i in range(1, e + 1):
        for j in range(i * 2, e + 1, i):  # i의 배수에 대해
            cnt[j] += 1  # i는 j의 약수이므로 증가

    #dp[n] : [n,e]에서 약수의 개수가 가장 많은 수
    dp = [0] * (e + 1)
    dp[e] = e  # 마지막 값은 자기 자신
    for i in range(e - 1, 0, -1):
        # 더 많이 등장한 숫자를 선택
        if cnt[i] >= cnt[dp[i + 1]]:
            dp[i] = i
        else:
            dp[i] = dp[i + 1]

    answer = [dp[start] for start in starts]
    return answer