프로그래머스 (월간 코드 챌린지 시즌2) - 약수의 개수와 덧셈
해당 문제는 약수를 구하는 알고리즘을 통해 약수의 개수를 구함으로서 빠르게 풀 수 있었습니다. 이전이라면 1~n까지 반복문을 돌며 n을 나눈 나머지가 0인 것을 약수로 판단하였는데, 지금은 제곱근을 구하고 1부터 제곱근(sqrt(n)) 까지의 반복문중 나머지가 0인 것과 몫이 약수라는 것을 쉽게 구할 수 있었습니다.
public int solution(int left, int right) {
int answer = 0;
for (int i = left; i <=right; i++) {
answer = getDivisorCount(i) % 2 ==0 ? answer + i : answer - i;
}
return answer;
}
public int getDivisorCount(int num) {
int sqrt = (int) Math.sqrt(num);
int divisorCount = 0;
for (int i = 1; i <= sqrt; i++) {
if (num % i == 0) {
divisorCount++;
if(num / i != i) {
divisorCount++;
}
}
}
return divisorCount;
}
'정리 > 알고리즘' 카테고리의 다른 글
프로그래머스 - 다트 게임 (0) | 2022.05.02 |
---|---|
프로그래머스 - 삼진법 뒤집기 (0) | 2022.04.20 |
프로그래머스 - 소수만들기 (0) | 2022.04.18 |
프로그래머스 - [1차] 뉴스 클러스터링 (0) | 2022.04.13 |
프로그래머스 - 괄호 변환 (0) | 2022.04.13 |
댓글