문제 설명
두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주세요.
문제 핵심
이 문제를 풀 때 모든 숫자의 약수를 직접 세어도 된다.
하지만 더 간단한 규칙이 있다.
약수의 개수가 홀수인 수는 완전제곱수뿐이다.
완전제곱수란 어떤 정수를 자기 자신과 곱해서 만들 수 있는 수를 말한다.
예를 들면 다음과 같다.
1 = 1 × 1
4 = 2 × 2
9 = 3 × 3
16 = 4 × 4
25 = 5 × 5즉, 1, 4, 9, 16, 25 같은 수는 완전제곱수다.
왜 완전제곱수만 약수의 개수가 홀수일까?
보통 약수는 짝을 이루어 나온다.
예를 들어 12의 약수를 생각해 본다.
1 × 12
2 × 6
3 × 4약수는 다음과 같다.
1, 2, 3, 4, 6, 12총 6개다.
짝수 개다.
이번에는 16을 생각해 본다.
1 × 16
2 × 8
4 × 4약수는 다음과 같다.
1, 2, 4, 8, 16총 5개다.
홀수 개다.
4 × 4처럼 가운데 약수가 자기 자신과 짝을 이루기 때문에 약수의 개수가 홀수가 된다.
따라서 완전제곱수는 약수의 개수가 홀수다.
풀이 아이디어
left부터 right까지 반복하면서 각 숫자가 완전제곱수인지 확인한다.
- 완전제곱수라면 약수의 개수가 홀수이므로 뺀다.
- 완전제곱수가 아니라면 약수의 개수가 짝수이므로 더한다.
완전제곱수인지 확인하려면 제곱근을 구한 뒤 다시 제곱해 보면 된다.
예를 들어 16의 제곱근은 4다.
4 × 4 = 16따라서 16은 완전제곱수다.
반대로 17의 제곱근을 정수로 바꾸면 4다.
4 × 4 = 16원래 숫자인 17과 다르다.
따라서 17은 완전제곱수가 아니다.
Java 코드
class Solution {
public int solution(int left, int right) {
int answer = 0;
for (int i = left; i <= right; i++) {
int sqrt = (int) Math.sqrt(i);
if (sqrt * sqrt == i) {
answer -= i;
} else {
answer += i;
}
}
return answer;
}
}코드 설명
int answer = 0;최종 결과를 저장할 변수다.
더하거나 뺀 결과가 이 변수에 누적된다.
for (int i = left; i <= right; i++)left부터 right까지 숫자를 하나씩 확인한다.
예를 들어 left = 13, right = 17이면 다음 숫자들을 차례대로 확인한다.
13, 14, 15, 16, 17int sqrt = (int) Math.sqrt(i);현재 숫자 i의 제곱근을 구한다.
Math.sqrt(i)는 제곱근을 구해 주는 메서드다.
예를 들어 i가 16이면 다음과 같다.
Math.sqrt(16) = 4if (sqrt * sqrt == i)구한 제곱근을 다시 제곱했을 때 원래 숫자와 같은지 확인한다.
같다면 완전제곱수다.
4 × 4 = 16따라서 16은 완전제곱수다.
answer -= i;완전제곱수는 약수의 개수가 홀수이므로 뺀다.
answer += i;완전제곱수가 아니라면 약수의 개수가 짝수이므로 더한다.
예시
입력값이 다음과 같다고 해 보자.
left = 13
right = 17숫자를 하나씩 확인한다.
13 → 완전제곱수 아님 → 더한다
14 → 완전제곱수 아님 → 더한다
15 → 완전제곱수 아님 → 더한다
16 → 완전제곱수 맞음 → 뺀다
17 → 완전제곱수 아님 → 더한다계산식은 다음과 같다.
13 + 14 + 15 - 16 + 17 = 43따라서 결과는 43이다.
정리
이 문제는 약수의 개수를 직접 세는 방식으로도 풀 수 있다.
하지만 완전제곱수의 특징을 알면 훨씬 간단하게 풀 수 있다.
핵심은 다음 한 줄이다.
완전제곱수면 빼고, 아니면 더한다.약수의 개수가 홀수인 수는 완전제곱수뿐이라는 규칙을 이용하면 반복문 안에서 간단하게 조건을 처리할 수 있다.
