약수의 개수가 홀수인가?

#include <string>
#include <vector>
#include <cmath>

using namespace std;

// Number의 약수 개수를 반환
int GetDivisorCount(int Number)
{
    int Count = 0;
    
    for(int i = 1 ; i <= sqrt(Number); ++i)
    {
        if(Number % i == 0)
        {
            if(i == Number / i)
            {
                Count += 1;
            }
            else
            {
                Count += 2;
            }
        }
    }
    
    return Count;
}

int solution(int left, int right) 
{
    int answer = 0;
    
    for(int Num = left; Num <= right; ++Num)
    {
        //Num의 약수 개수 구하기
        int Count = GetDivisorCount(Num);
        //약수가 홀수인지, 짝수인지 판단해서 answer에 계산
        answer += (Count % 2 == 0) ? Num : Num * -1;
    }
    return answer;
}

처음 이 문제를 접했을 때, 현재 타겟 숫자의 약수 개수를 리턴하는 함수를 만들어서 약수가 홀수라면 값을 빼고 짝수라면 더하는 구조로 문제의 어순 흐름대로 해결해보았다.

 

하지만 깊게 생각해보면 약수가 홀수라는 얘기는 약수 중에 제곱수가 포함되어있다는 얘기가 되고, 이 전제라면 직접 약수의 개수를 Counting 하지 않고 타겟 숫자가 제곱수를 포함하고 있는지 여부만 확인하면 된다는 이야기이다.

 

 

 

#include <string>
#include <vector>
#include <cmath>

using namespace std;


int solution(int left, int right) 
{
    int answer = 0;
    
    for(int Num = left; Num <= right; ++Num)
    {   
        //타겟 숫자의 제곱수 계산
        int SquareNumber = sqrt(Num);
        
        //계산한 제곱수가 실질적으로 제곱을 했을 때, 타겟 숫자가 나오는지 확인
        //맞다면 약수가 홀수임으로 값을 빼고, 아니라면 약수가 짝수임으로 값을 더한다
        answer += (Num == SquareNumber * SquareNumber) ? Num * -1 : Num;
    }
    
    return answer;
}

이와 같이 범위 중 현재 타겟 숫자의 제곱수를 계산한 후, 계산된 제곱수를 다시 제곱을 해서 실질적인 제곱수가 맞는지 확인한다. 맞다면 타겟 숫자는 제곱수를 갖고 있기 때문에 약수의 개수가 홀수가 되고, 아니라면 약수의 개수는 짝수가 된다.

 

이렇게 계산하였을 때 코드가 더 간결해보이고, 약수를 계산해 카운팅 하는 방식에 비해 제곱수만 계산해서 확인함으로 더 빠른 장점이 있다.

 

추가적으로 제곱수인지 확인할 때, std::pow를 사용할까도 했지만 부동소수점 연산이 필요하지 않고 단순 제곱수인지 확인만 하는 과정이기에 직접 연산하는게 더 효율적이다.