[프로그래머스] 약수의 개수와 덧셈

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

코딩테스트 연습 - 약수의 개수와 덧셈

---

 

-풀이-

약수의 개수를 return 해주는 get_cnt함수를 선언해주었다.

int get_cnt(int n){
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(n%i==0) cnt++;
    }
    return cnt;
}

약수를 구해야하는 최고로 큰 수가 1000이여서 1~N까지 탐색하며 나누어지는 약수를 세어주는 알고리즘을 사용했다.

 

이 함수를 left~right까지 넣어서 return 되는 개수가 짝수면 answer에 그 값을 더해주고, 홀수면 빼주었다.

 

-시간복잡도-

left=1 , right=1000인 상황이 최악의 상황이다. 이 크기를 N이라고 하면, 약수를 구하는 시간복잡도도 O(N)이 되기떄문에 , 최종 시간복잡도는 O(N²)이 된다.

 

-코드-

 

#include <string>
#include <vector>

using namespace std;

int get_cnt(int n){
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(n%i==0) cnt++;
    }
    return cnt;
}

int solution(int left, int right) {
    int answer = 0;
    for(int i=left;i<=right;i++){
        get_cnt(i)%2==0 ? answer+=i : answer-=i;
    }
    return answer;
}