[프로그래머스] Level1 기사단원의 무기(with python)
https://school.programmers.co.kr/learn/courses/30/lessons/136798
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
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