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

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

프로그래머스

해설

일단 억억단에서 등장하는 횟수는 약수의 개수와 같다.

고로 약수를 빠르게 얻는법을 알아야 한다.

약수를 얻은 다음에 (숫자,약수) 를 조건에 맞게 sort해준뒤 값을 구한다.

 

약수 빠르게 구하는법은 추후 정리.

 

10번문제가 채점 서버의 상태에따라 통과되기도 하고 안하기도 한다. 다른사람 풀이를 돌려봐도 마찬가지...

divisor = [0] * 5000001
def solution(e, starts):
    for i in range(2,e+1):
        for j in range(1,min(e//i+1,i)):
            divisor[i*j]+=2
    for i in range(1,int(e**(1/2))+1):
        divisor[i**2]+=1
    answer = []
    hq = []
    minVal = min(starts)
    for number in range(minVal,e+1):
        hq.append((-divisor[number],number))

    hq.sort()
    for s in starts:
        for t in hq:
            if s <= t[1]:
                answer.append(t[1])
                break
    return answer

 

혹은 아래처럼 약수를 깔끔하게..

 

divisor = [1] * 5000001
def solution(e, starts):
    for i in range(2,e+1):
        for j in range(i,e+1,i):
            divisor[j]+=1
    answer = []
    hq = []
    minVal = min(starts)
    for number in range(minVal,e+1):
        hq.append((-divisor[number],number))

    hq.sort()
    for s in starts:
        for t in hq:
            if s <= t[1]:
                answer.append(t[1])
                break
    return answer