[프로그래머스][C++] 약수의 개수와 덧셈

약수의 개수와 덧셈

문제 링크

약수의 개수와 덧셈

분석

약수의 개수를 구하고, 개수가 짝수라면 더하고, 홀수라면 뺀 수의 결과값을 반환하는 문제입니다.

반복문으로 개수를 구하고, 개수가 짝수인지 홀수인지 확인하는 방법이 있습니다.
다른 방법으로는 약수를 구하는 수가 완전 제곱수가 있을경우 약수의 개수가 홀수이므로, 이 방법을 사용 할 수 도 있습니다.

풀이

반복문으로 약수의 개수를 구하는 방법입니다.

int solution(int left, int right) {
    int answer = 0;
    
    for (int i = left; i <= right; ++i)
    {
        int count = 0;
        
        for (int j = 1; j * j <= i; ++j)
        {
            if (i % j != 0)
            {
                continue;
            }
            
            if (i / j == j)
            {
                count += 1;
            }
            else
            {
                count += 2;
            }
        }
        
        if (count % 2 == 0)
        {
            answer += i;
        }
        else
        {
            answer -= i;
        }
    }
    
    return answer;
}

i는 left에서 rifht까지 순회합니다.

j는 i에 대해 순회하며, 약수를 구합니다.

j * j인 이유는 약수 쌍을 계산해 효율적으로 반복문의 횟수를 유의미하게 줄이기 위함입니다.
약수의 쌍을 찾아 2개씩 저장하기 때문에 반복문의 횟수를 줄일 수 있습니다.

i % j != 0일 경우 약수가 아니므로 넘어갑니다.

i / j == j일 경우 제곱근이므로 약수의 개수를 1만 증가시킵니다.
만약 제곱근이 아니라면 약수쌍까지 2씩 증가시킵니다.

이후 약수의 개수를 다 구했다면 개수가 홀수인지 짝수인지 확인해 answer의 값을 수정합니다.

---

완전 제곱수로 약수의 개수가 홀수인지 판별하는 방법입니다.

#include <cmath>

int solution(int left, int right) {
    int answer = 0;
    
    for (int i = left; i <= right; ++i)
    {
        int sqrtValue = sqrt(i);
        
        if (sqrtValue * sqrtValue == i)
        {
            answer -= i;
        }
        else
        {
            answer += i;
        }
    }
    
    return answer;
}

i의 제곱근을 구하고 해당 제곱근을 정수로 저장합니다.
정수로 저장된 이 값을 제곱했을 때 i와 같다면 완전 제곱수입니다.

완전 제곱수를 가진 수라면 홀수이므로 빼줍니다.
가지지 않은 수라면 짝수이므로 더해줍니다.

성능 요약

반복문으로 약수의 개수를 구한 방법의 성능입니다.

테스트 1 〉 통과 (0.13ms, 4.43MB)
테스트 2 〉 통과 (0.04ms, 4.44MB)
테스트 3 〉 통과 (0.04ms, 4.21MB)
테스트 4 〉 통과 (0.01ms, 4.2MB)
테스트 5 〉 통과 (0.09ms, 4.22MB)
테스트 6 〉 통과 (0.01ms, 3.67MB)
테스트 7 〉 통과 (0.01ms, 4.27MB)

---

제곱근을 구하고, 완전 제곱수로 약수의 개수가 짝수인지 홀수인지 판별한 방법의 성능입니다.

테스트 1 〉 통과 (0.01ms, 4.22MB)
테스트 2 〉 통과 (0.01ms, 4.15MB)
테스트 3 〉 통과 (0.01ms, 4.22MB)
테스트 4 〉 통과 (0.01ms, 4.16MB)
테스트 5 〉 통과 (0.01ms, 4.15MB)
테스트 6 〉 통과 (0.01ms, 4.14MB)
테스트 7 〉 통과 (0.01ms, 4.23MB)