문제 조건
- 1부터 number까지의 약수의 갯수를 구해야함
- 약수구하기를 1부터 N까지 모두 계산해서 구하면 (O(n)) 시간초과
- N의 약수를 구할 때, √N까지 구하면 약수 절반의 갯수를 구할 수 있음
- √N만큼의 약수의 갯수를 구하고 * 2
만약 √N이 제곱근이 된다면 구한 약수의 갯수에 +1 - 이 방법으로 시간을 O(√n)을 단축할 수 있음
문제 풀이
- weapons배열을 만들어 number만큼 약수의 갯수 값을 저장함
- 약수의 갯수 구하기는 J*J = I 가 될때까지,
즉 제곱근이 되는 숫자가 될 때 까지 계산해주면 됨 - 만약 약수의 갯수가 limit보다 넘어가면, power 값을 answer에 더해주고,
limit과 같거나 적으면, 해당 약수의 값을 answer에 더해준다. - 모든 계산이 끝나면 answer값 리턴
https://school.programmers.co.kr/learn/courses/30/lessons/136798
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
참고자료
[Java] 약수의 개수 구하기
방법1 N의 약수 개수 구하는 방법을 생각했을 때 바로 떠오르는 방법은 N을 1부터 N까지의 숫자로 나눠 약수인지 판별하여 카운트를 해주는 방법이다. 코드로 구현해보면 아래와 같다. int N = 100000
chwan.tistory.com
'Algorithms > Programmers' 카테고리의 다른 글
| [Programmers] 콜라 문제 (0) | 2022.11.21 |
|---|---|
| [Programmers] 옹알이 (2) (0) | 2022.11.21 |
| [Programmers] 햄버거 만들기 (0) | 2022.11.21 |
| [Programmers] 푸드 파이트 대회 (0) | 2022.11.20 |
| [Programmers] 과일장수 (0) | 2022.11.20 |