[프로그래머스] Level1 기사단원의 무기(with python)

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

프로그래머스

 

1. 내가 작성한 코드

def solution(number, limit, power):
 
 result = 0
  
    for j in range(1, number+1):
        cnt = 0
        for i in range(1,int(j**0.5)+1):
            if j % i == 0:
                if i == (j//i):
                    cnt+=1
                else:
                    cnt+=2
                    
        if cnt <= limit:
            result += cnt
        else:
            result += power
        
    return result

 

소인수분해를 이용해서 문제를 해결하면 number 전체를 탐색해야 하기 때문에 시간초과로 실패하게 된다.

 

열심히 구글링을 해본 결과, 약수를 구하는 방법으로 "제곱근"을 이용하는 방법이 있음을 알게됐다.

 

결론부터 말하면, 이 제곱근을 이용하면 시간이 훨씬 단축된다.

 

 

1. 제곱근을 이용해서 약수 구하기

 

예를 들어서 20의 약수는 1,2,4,5,10,20이고, 제곱근은 4.472... 즉, 정수로 바꿔주면 4가 된다.

20을 1부터 제곱근인 4까지로 각각 나눠주면 

 

20 % 1 == 0

20 % 2 == 0

20 % 3 != 0

20 % 4 == 0

 

가 되고, 20을 1,2,4로 나눈 수(20,10,5)를 함께 구할 수 있다. 

 

본 방법을 이용하면 number 전체를 탐색할 필요 없어 시간복잡도가 감소된다.

 

(참고로 python의 range 함수 특성때문에 int(j**0.5) + 1 을 해준 것

 

 

2. 제곱수인 경우

 

이 때, 제곱수(4,9,16..)인 경우에서는 cnt가 1개만 증가하는 문제점이 발생한다.

 

ex) 16의 약수는 1,16 / 2,8 / 4 

 

따라서 아래 코드를 이용해 조건문을 걸어줌으로써 본 문제를 해결할 수 있다.

if i == (j//i):
	cnt+=1
else:
	cnt+=2