반응형
# Problem
두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주세요.
제한사항
- 1 ≤ left ≤ right ≤ 1,000
입출력 예
left | right | result |
13 | 17 | 43 |
24 | 27 | 52 |
입출력 예 설명
입출력 예 #1
- 다음 표는 13부터 17까지의 수들의 약수를 모두 나타낸 것입니다.
수 | 약수 | 약수의 개수 |
13 | 1, 13 | 2 |
14 | 1, 2, 7, 14 | 4 |
15 | 1, 3, 5, 15 | 4 |
16 | 1, 2, 4, 8, 16 | 5 |
17 | 1, 17 | 2 |
- 따라서, 13 + 14 + 15 - 16 + 17 = 43을 return 해야 합니다.
입출력 예 #2
- 다음 표는 24부터 27까지의 수들의 약수를 모두 나타낸 것입니다.
수 | 약수 | 약수의 개수 |
24 | 1, 2, 3, 4, 6, 8, 12, 24 | 8 |
25 | 1, 5, 25 | 3 |
26 | 1, 2, 13, 26 | 4 |
27 | 1, 3, 9, 27 | 4 |
- 따라서, 24 - 25 + 26 + 27 = 52를 return 해야 합니다.
# My Answer
def solution(left, right):
answer = 0
for i in range(left,right+1):
temp=2
if i==1:
answer-=1
elif i==2:
answer+=2
else:
for j in range(2,i):
if i%j==0:
temp+=1
if temp%2==0:
answer+=i
else:
answer-=i
return answer
1일 때 약수는 한개
2일 때 약수는 2개
3부터는 1과 자기자신을 제외하고 약수의 개수를 더해서 temp에 저장
temp가 짝수면 answer에 더해주고, 홀수면 빼주기
# Solution 1
def solution(left, right):
answer = 0
for i in range(left,right+1):
if int(i**0.5)==i**0.5:
answer -= i
else:
answer += i
return answer
제곱수의 약수의 개수는 항상 홀수
약수는 짝을 이루어서 곱해지는데, 6의 제곱인 숫자 36의 예를 들어보면
1 * 36
2 * 18
3 * 12
4 * 9
6 * 6
으로 마지막 6은 짝이 없게 된다. 1,2,3,4,6,9,12,18,36 으로 9개의 약수를 가진다.
이와같이 제곱수의 약수의 개수는 항상 홀수 ( 제곱하는 수의 짝이 없음 )
반응형
'Algorithm > Programmers Lv.1' 카테고리의 다른 글
[코딩테스트 연습] 2016년 (0) | 2021.06.06 |
---|---|
[2021 Dev-Matching] 로또의 최고 순위와 최저 순위 (0) | 2021.06.05 |
[월간 코드 챌린지 시즌2] 음양 더하기 (zip()함수) (0) | 2021.05.31 |
[2021 KAKAO BLIND RECRUITMENT] 신규 아이디 추천 ( 정규 표현식 ) (0) | 2021.05.31 |
[코딩테스트 연습] 행렬의 덧셈 ( zip 함수 ) (0) | 2021.05.29 |