https://programmers.co.kr/learn/courses/30/lessons/77884
코딩테스트 연습 - 약수의 개수와 덧셈
두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주
programmers.co.kr
left부터 right 수 까지의 모든 수에 대한 약수를 리스트에 추가한 후 리스트 요소의 개수가 짝수이면 answer에 더하고 홀수면 빼는 로직을 구현해야 한다.
이렇게 문제에 나온 논리 그대로 코드를 구현하면 다음과 같다.
구현 자체는 굉장히 쉽지만 다른 사람의 풀이에서 좋은 아이디어를 얻었기에 이를 기억하고자 포스팅을 작성했다.
> 배운 점
약수의 개수가 홀수인 수는 제곱수이다.
몇 가지 경우를 생각해보자
16의 약수 = [1,2,4,8,16] 으로 다섯개의 약수를 가진다.
5의 약수 = [1,5]로 두개의 약수를 가진다.
25의 약수= [1,5,25]로 세개의 약수를 가진다.
이 원리를 활용해 코드를 다시 짜보면 다음과 같다.
* 제곱수의 제곱근은 정수로 떨어지는 반면, 제곱수가 아닌 수의 제곱근은 소수로 나온다.
'python > 알고리즘 문제풀이' 카테고리의 다른 글
| [백준 | 파이썬3] 1874 스택 수열 (0) | 2022.02.28 |
|---|---|
| [백준 | 파이썬3] 10814 나이 순 정렬 (0) | 2022.02.23 |
| [프로그래머스 | 파이썬3] 실패율 - 정렬 (0) | 2021.12.08 |
| [백준 | 파이썬3] 1018. 체스판 다시 칠하기 - 브루트포스 (1) | 2021.12.07 |
| [백준 | 파이썬3] 1541. 잃어버린 괄호- 그리디알고리즘 (2) | 2021.12.06 |