[Lv.1] 기사단원의 무기 [프로그래머스_코딩테스트] [수학, 구현] [30분]

🔍 문제 요약

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

프로그래머스

number라는 숫자를 주어지고 1부터 숫자를 늘려가면서 각 숫자들의 약수의 개수를 구하고, limit을 초과한 경우 power로 kg을 매겨서 합산 kg을 구하는 문제

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

숫자의 약수를 구하는 식 자체는 단순하게 생각해서 그냥 숫자의 반절까지 반복문을 돌리면서 나눠보면 된다. 문제의 풀이 자체는 어렵지 않다고 생각했는데 최적화를 고려한 부분은 피드백을 받아보기로 하였다. 문제는 일단 전체 테스트 케이스 성공이 뜨긴 함. (다만 time limit 걸릴 거 같은 아슬아슬하게 통과된 부분들이 있어 보인다.)

using System;

public class Solution
{
    /// <summary>
    /// 기사단원의 무기
    /// https://school.programmers.co.kr/learn/courses/30/lessons/136798
    /// </summary>
    public int solution(int number, int limit, int power)
    {
        // number 반복 돌리면서 약수 개수 체크
        // limit 넘기는 지 체크
        int[] numArr = new int[number];

        for (int i = 1; i <= number; i++)
        {
            // 자기 자신은 무조건 약수에 포함이므로 넣기
            int count = 1;
            
            // 계산을 줄이기 위해서 반절만 계산
            for (int j = 1; j <= (i / 2); j++)
            {
                if (i % j == 0)
                {
                    count++;

                    // limit을 넘긴 경우 power로 제한
                    if (count > limit)
                    {
                        count = power;
                        break;
                    }
                }
            }

            numArr[i - 1] = count;
        }
        
        int answer = 0;

        foreach (var num in numArr)
        {
            answer += num;
        }
        
        return answer;
    }
}

/// <summary>
/// C# 7.3
/// </summary>
internal class Program
{
    public static void Main(string[] args)
    {
        var sl = new Solution();
        int number1 = 5;
        int limit1 = 3;
        int power1 = 2;
        int number2 = 10;
        int limit2 = 3;
        int power2 = 2;
        Console.WriteLine(sl.solution(number1, limit1, power1));
        Console.WriteLine(sl.solution(number2, limit2, power2));
    }
}

✅ 풀이 코드

public int solution(int number, int limit, int power)
{
    int answer = 0;

    for (int i = 1; i <= number; i++)
    {
        int count = 0;
        int sqrt = (int)Math.Sqrt(i);

        for (int j = 1; j <= sqrt; j++)
        {
            if (i % j == 0)
            {
                // j와 i/j가 다르면 둘 다 약수
                if (j == i / j) count++;
                else count += 2;
            }
        }

        // limit 넘으면 power로 대체
        answer += (count > limit) ? power : count;
    }

    return answer;
}

모든 약수는 쌍으로 존재하기에 제곱근까지만 계산하면 남은 반절은 자동으로 개수 추가를 할 수 있다고 한다. 추가로 필자는 배열에 개수를 다 집어넣고 더하는 방식을 하다 보니 메모리 차지도 하게 되었는데 이 부분도 바로 더해가는 방식으로 계산할 수 있다. 

🔄 정리

약수의 쌍 성질을 기억해두면 정말 유용할 것 같다. 간단히 숫자의 절반으로만 생각했었던 것을 생각해보면 제곱근까지만 계산을 하고 개수를 2개씩 카운트 시키면 되었던 것. (예시의 16에서 4, 4의 케이스인 경우에만 1개)