[프로그래머스][C++] 기사단원의 무기

기사단원의 무기

문제 링크

기사단원의 무기

분석

약수의 개수를 구해 값을 저장하고, 총합을 반환하는 문제입니다.

만약 약수의 개수가 limit보다 크다면 power의 값을 사용해 값을 저장합니다.

number와 power의 값은 1 이상입니다.
limit의 값은 2 이상입니다.

풀이

#include <vector>

using namespace std;

int solution(int number, int limit, int power) {
    int answer = 0;
    
    for (int i = 1; i <= number; ++i)
    {
        // 약수의 개수
        int divisorCount = 0;
        
        // 약수를 구하는 반복문
        for(int j = 1; j * j <= i; ++j)
        {
            // j가 약수인 경우
            if (i % j == 0)
            {
                ++divisorCount;
                
                // 완전 제곱수를 제외한 짝을 이루는 약수
                if (i / j != j)
                {
                    ++divisorCount;
                }
            }
            
            // 약수의 개수가 limit을 초과하면 power 사용
            if (divisorCount > limit)
            {
                divisorCount = power;
                break;
            }
        }
        
        // 약수의 개수 총합
        answer += divisorCount;
    }
    
    return answer;
}

1부터 number까지 약수 개수의 총합을 구해야하므로 순회합니다.

i번째에 해당하는 약수의 개수를 구합니다.
1부터 i까지 나누는 것보다 제곱근까지만 탐색하는 방식이 효율적이므로 제곱근까지만 탐색합니다.

i % j == 0가 참이면 약수이므로, j와 i / j가 약수입니다.

i / j != j에서 != j를 확인하는 것은 완전제곱수인 경우 같은 값이 중복 카운트 되지 않도록 하기 위함입니다.

divisorCount > limit를 확인해 약수의 개수가 초과일 경우 power값으로 대체한 후 반복문을 탈출합니다.

성능 요약

시간 복잡도는 $O(n \sqrt{n})$의 시간 복잡도를 가집니다.

• number 순회 ($O(n)$)
• 약수를 구하는 반복문 ($(\sqrt{n}))

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

테스트 1 〉 통과 (2.02ms, 4.2MB)
테스트 2 〉 통과 (0.25ms, 4.22MB)
테스트 3 〉 통과 (0.10ms, 3.68MB)
테스트 4 〉 통과 (0.34ms, 4.45MB)
테스트 5 〉 통과 (0.07ms, 4.11MB)
테스트 6 〉 통과 (1.97ms, 4.14MB)
테스트 7 〉 통과 (0.26ms, 3.72MB)
테스트 8 〉 통과 (0.16ms, 4.18MB)
테스트 9 〉 통과 (1.83ms, 3.68MB)
테스트 10 〉 통과 (0.10ms, 3.68MB)
테스트 11 〉 통과 (51.01ms, 4.12MB)
테스트 12 〉 통과 (54.86ms, 3.68MB)
테스트 13 〉 통과 (27.71ms, 4.21MB)
테스트 14 〉 통과 (54.71ms, 4.15MB)
테스트 15 〉 통과 (57.40ms, 3.63MB)
테스트 16 〉 통과 (45.93ms, 4.22MB)
테스트 17 〉 통과 (0.01ms, 3.64MB)
테스트 18 〉 통과 (8.58ms, 4.18MB)
테스트 19 〉 통과 (0.25ms, 4.21MB)
테스트 20 〉 통과 (0.23ms, 4.02MB)
테스트 21 〉 통과 (0.01ms, 3.66MB)
테스트 22 〉 통과 (0.01ms, 4.2MB)
테스트 23 〉 통과 (0.01ms, 4.13MB)
테스트 24 〉 통과 (63.40ms, 3.58MB)
테스트 25 〉 통과 (59.60ms, 4.11MB)
테스트 26 〉 통과 (0.06ms, 3.65MB)
테스트 27 〉 통과 (0.06ms, 4.21MB)