[Lv.1] 약수의 개수와 덧셈 [프로그래머스_코딩테스트] [수학] [20분]

🔍 문제 요약

https://school.programmers.co.kr/learn/courses/30/lessons/77884

프로그래머스

숫자 left, right가 주어지고 left부터 right까지 약수의 개수가 짝수이면 더하고 홀수이면 빼서 합산을 구하는 문제

🧠 나의 접근 방식과 시행착오

단순하게 생각하면 left부터 right까지 반복을 돌리면서 약수를 일일이 다 구해보는 것. 숫자가 크게 되면 시간이 꽤나 소모되는 걸로 생각. 그래서 기존에 문제를 풀면서 다뤘던 약수를 구할 때는 제곱근까지만 구하면 된다는 것을 풀이에 적용했다. 그렇게 하면 계산을 반절 이하로 낮출 수 있어서 좀 더 빠르게 가능. 10분~15분 정도 걸림

using System;

public class Solution
{
    /// <summary>
    /// 약수의 개수와 덧셈
    /// </summary>
    public int solution(int left, int right)
    {
        int sum = 0;
        
        // 정직하게 약수를 구해보고 더하고 빼기
        for (int num = left; num <= right; num++)
        {
            // 최적화 : 약수는 항상 쌍으로 존재해서  num 의 제곱근 까지만 계산을 하고 2배를 해주면 됨. 
            var calcNum = (int)Math.Sqrt(num);
            
            // 1과 자기 자신은
            int count = 0;
            for (int j = 1; j < calcNum; j++)
            {
                if (num % j == 0)
                {
                    count++;
                }
            }

            count *= 2;

            if (calcNum * calcNum == num)
            {
                count += 1;
            }

            sum += (count % 2 == 0 ? num : -num);
        }
        
        return sum;
    }
}

/// <summary>
/// C# 7.3
/// </summary>
internal class Program
{
    public static void Main(string[] args)
    {
        var sl = new Solution();
        var leftAndRight1 = new [] { 13, 17 };
        var leftAndRight2 = new [] { 24, 27 };
        Console.WriteLine(sl.solution(leftAndRight1[0], leftAndRight1[1]));
        Console.WriteLine(sl.solution(leftAndRight2[0], leftAndRight2[1]));
    }
}

✅ 풀이 코드

사실 이 문제의 풀이는 더 할 필요가 없다고 생각을 했었었다. 피드백을 보기 전까진 그랬다.. 생각이 짧았다고 여겼던 것 중 하다가 제곱근까지 구하면 효율이 좋다는 것을 알았을 때 쌍의 성질이 있다는 것도 주석에 적어두었었다. 다만 이것까지 생각해두고 이게 홀수일 지 짝수일지를 생각하는 것은 단순한 거였는데 생각을 놓쳫다는 점... 제곱근을 구했을 때 정수가 나오는 상태라면 약수의 개수는 홀수가 된다.. 당연하게도.. 그래서 아래의 풀이처럼 매우 간단하게 풀 수 있는 문제.

public int solution(int left, int right)
{
    int sum = 0;
    for (int i = left; i <= right; i++)
    {
        int sqrt = (int)Math.Sqrt(i);
        sum += (sqrt * sqrt == i) ? -i : i;
    }
    return sum;
}

🔄 정리

어떻게 보면 정말 한 번 더 생각을 해봤으면 좀 더 최적화된 로직으로 풀 수 있었을 문제. 약수의 개수가 짝수인지 홀수인지는 제곱근의 값이 정수로 떨어진다로 체크하면 된다.