※[프로그래머스]Lv.1 기사단원의 무기 C# (약수의개수,시간복잡도개선)

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

프로그래머스

소스코드1처럼 제출을 하면 타임에러가 나게된다. 소스코드2 처럼 연산을 줄여서 제출해야한다.

 

N의 가장 큰 약수는 N을 제외하면 최대 N의 절반이기 때문이다. if (i / j == j) 문은 마지막의 수이며 이를 제외하면 count는 2개씨 존재한다.

 

소스코드 1(오류)

using System;

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

        for (int i = 1; i <= number; i++)
        {
            int count = 0;

            for (int j = 1; j <= number; j++)
                if (i % j == 0)
                    count++;

            if (count <= limit)
                answer += count;
            else
                answer += power;
        }
        return answer;
    }
}

소스코드 2(개선)

using System;

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

        for (int i = 1; i <= number; i++)
        {
            int count = 0;
            for (int j = 1; j * j <= i; j++)
            {
                if (i % j == 0)
                {
                    if (i / j == j)
                    {
                        count++;
                    }
                    else
                    {
                        count += 2;
                    }
                }
            }

            if (count <= limit)
                answer += count;
            else
                answer += power;
        }
        return answer;
    }
}