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

1차 풀이

def nums(x):
    q = []
    for i in range(1,x//2+1):
        if x % i ==0:
            q.append(i)

    q.append(x)
    ans = len(q)
    return ans


def solution(e, starts):
    answer = []

    for i in starts:
        q = []
        for j in range(i,e+1):
            q.append(nums(j))
        answer.append( q.index(max(q))+i )

    print(answer)

    return answer

시간 초과가 발생했다.

2차 풀이

def nums(x):
    q = []
    q_back = []
    for i in range(1,int(x**(1/2)) + 1):
        if x % i ==0:
            q.append(i)
            if i!= (x//i):
                q_back.append(x//i)

    q = q+q_back[::-1]
    ans = len(q)
    return ans


def solution(e, starts):
    answer = []

    for i in starts:
        q = []
        for j in range(i,e+1):
            q.append(nums(j))
        answer.append( q.index(max(q))+i )

    print(answer)

    return answer

약수를 구하는 함수를 제곱근을 활용하여 효율성을 높였다.

속도가 훨씬 빨라졌지만 여전히 시간 초과가 발생했다.

3차 풀이

def solution(e, starts):
    answer = []
    dp = [0] * (e + 1)
    dp_idx = [0] * (e + 1)

    for i in range(2,e+1):
        for j in range(1,min(e//i+1,i)):
            dp[i*j]+=2
    for i in range(1,int(e**(1/2))+1):
        dp[i**2]+=1



    max_count = 0
    for i in range(e, 0, -1):
        if max_count <= dp[i]:
            max_count = dp[i]
            dp_idx[i] = i
        else:
            dp_idx[i] = dp_idx[i + 1]

    for i in starts:
        answer.append(dp_idx[i])

    print(answer)

    return answer

시간복잡도를 고려하여 약수 구하는 방식을 바꿨다.

약수의 갯수 구하는 공식은 알아두면 좋을것 같다.

    dp = [0] * (e + 1)
    for i in range(2,e+1):
        for j in range(1,min(e//i+1,i)):
            dp[i*j]+=2
    for i in range(1,int(e**(1/2))+1):
        dp[i**2]+=1