약수의 개수와 덧셈

문제 요약

left부터 right까지의 수 중, 약수의 개수가 짝수이면 더하고 홀수이면 빼서 반환하는 문제.

---

처음 접근 - 뭘 몰랐나

약수 개수가 홀수인 수가 뭔지 몰랐다

약수는 쌍으로 존재하기 때문에 보통 짝수개다.
예) 12의 약수: (1, 12), (2, 6), (3, 4) → 6개

그럼 홀수개가 되는 경우는 언제일까?
바로 완전제곱수일 때다.

예) 9의 약수: 1, 3, 9 → 3개 (3이 쌍 없이 혼자)

즉, 완전제곱수 = 약수 개수 홀수 = 빼야 하는 수

---

첫 번째 시도 - 완전제곱수 판별

내 코드

class Solution {
    public int solution(int left, int right) {
        int answer = 1; // ❌ 0이어야 함
        
        for (int i = left; i < right; i++) { // ❌ i <= right 여야 함
            int cnt = 1;
            while (cnt < i) {
                if (Math.pow(cnt) == i) { // ❌ 인자 2개 필요, double 비교 위험
                    answer += i; // ❌ 완전제곱수는 빼야 함
                }
                i++; // ❌ i를 건드리면 안 됨, cnt++ 이어야 함
            }
            answer -= i;
        }
        return answer;
    }
}

문제점 정리

문제	원인	수정
answer = 1	초기값 오류	answer = 0
i < right	right 미포함	i <= right
Math.pow(cnt)	인자 1개만 전달	Math.pow(cnt, 2)
Math.pow() double 비교	부동소수점 오차 위험	cnt * cnt == i 로 교체
i++	순회 변수를 내부에서 수정	cnt++
answer += i	완전제곱수는 빼야 함	조건 반전

---

두 번째 시도 - 로직 구조 문제

for (int i = left; i <= right; i++) {
    int cnt = 1;
    while (cnt < i) {
        if (cnt * cnt == i) {
            answer += i; // 완전제곱수인데 더함 ❌
            break;
        }
        cnt++;
    }
    answer -= i; // while과 무관하게 무조건 뺌 ❌
}

문제: 완전제곱수를 찾아서 더하고, 그 다음에 무조건 빼버림 → 이중 처리

---

세 번째 시도 - break 후 cnt 활용

while (cnt * cnt <= i) {
    if (cnt * cnt == i) {
        answer -= i;
        break;
    }
    cnt++;
}
if (cnt * cnt != i) {
    answer += i;
}

핵심 아이디어:

• 완전제곱수 발견 시 break → cnt가 해당 값에서 멈춤
• while 탈출 후 cnt * cnt == i 이면 완전제곱수 → 이미 뺐음
• cnt * cnt != i 이면 일반 수 → 더함

i=1 엣지케이스 문제

i=1일 때 while(cnt < 1) 조건으로 시작하면 루프를 아예 안 탐
→ cnt=1, 1*1 == 1 → 완전제곱수인데 빼지 않는 버그

수정: while(cnt * cnt <= i) 로 변경하면 해결
→ cnt=1, 1*1 <= 1 조건 만족, 1*1 == 1 → 정상 처리

---

최종 코드 1 - 완전제곱수 판별 (O(N√N))

class Solution {
    public int solution(int left, int right) {
        int answer = 0;
        
        for (int i = left; i <= right; i++) {
            int cnt = 1;
            while (cnt * cnt <= i) {
                if (cnt * cnt == i) {
                    answer -= i;
                    break;
                }
                cnt++;
            }
            if (cnt * cnt != i) {
                answer += i;
            }
        }
        return answer;
    }
}

Math.sqrt() 사용 시 double 문제를 피하려면:

int sqrt = (int) Math.sqrt(i);
if (sqrt * sqrt == i) // 안전한 완전제곱수 판별

---

최종 코드 2 - 브루트포스 (O(N²))

수학적 지식 없이도 약수를 직접 세는 방법으로 풀 수 있다.

class Solution {
    public int solution(int left, int right) {
        int answer = 0;
        
        for (int i = left; i <= right; i++) {
            int cnt = 0;
            for (int j = 1; j <= i; j++) {
                if (i % j == 0) {
                    cnt++;
                }
            }
            if (cnt % 2 == 0) {
                answer += i;
            } else {
                answer -= i;
            }
        }
        return answer;
    }
}

---

두 풀이 비교

	브루트포스	완전제곱수 판별
시간복잡도	O(N²)	O(N√N)
수학 지식	불필요	완전제곱수 개념 필요
가독성	직관적	약간 복잡
이 문제에서	✅ 통과 (범위 최대 1000)	✅ 통과

코테 팁: 범위가 작으면 브루트포스로 먼저 풀고, 최적화는 그 다음에 고민하자.

---

핵심 정리

• 완전제곱수 = 약수 개수 홀수 → 수학적으로 알면 O(N√N) 풀이 가능
• Math.pow() 대신 cnt * cnt 사용 → double 부동소수점 오차 회피
• Math.sqrt() 써야 한다면 (int) Math.sqrt(i) 로 캐스팅 후 재검증
• 모르면 일단 직접 세자 → 브루트포스도 충분한 경우가 많다