[Python] 기사단원의 무기 - 프로그래머스(Lv.1)

반응형

 

 

 

나의 문제 풀이

def solution(number, limit, power):
    lis = []
    for i in range(1,number+1):
        count = 0
        for j in range(1, int(i**(1/2)) + 1):
            if i%j == 0:
                count +=1
                if j < i//j:
                    count +=1
        if count > limit:
            lis.append(power)
        else:
            lis.append(count)
    return sum(lis)

 

시간 복잡도가 문제였던것 같습니다. 일반적으로 약수 구하는 공식을 썼을 경우에는 코드 실행부분은 통과해도 수가 굉장히 많이 커지면 런타임 에러로 통과를 할 수 없습니다. 그래서 약수를 더 효율적으로 빠르게 구할 수 있는 방법이 무엇인지 대해 많은 생각하면서 서치도 했었습니다. 

 

이러한 경우에는 약수를 구할 때 제곱근으로 구하면 됬었습니다. 이 공식은 에라토스테네스의 체입니다. 먼저 일반 약수를 구하는 것 처럼 i가 j로 나누어 지면 count를 하면 되고 거기다가 j가 i를 j로 나눈 것이 더 클 경우는 i//j가 약수가 되기 때문에 count를 1씩 증가합니다. 이러한 for문이 끝나고 나면 이젠 빈 리스트 lis에다가 count를 추가해 주면 되는데 만약 count가 limit모다 클 경우에는 power를 추가해 주어야 합니다. 

 

그리고 난후 for문을 완전히 돌리면 lis의 합을 구하면 됩니다.