프로그래머스 - 약수 구하기 - C++

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

프로그래머스

 

#include <string>
#include <vector>
#include <cmath>
using namespace std;

vector<int> solution(int n) {
    vector<int> answer;
    //for(int i=1;i<=n;i++)
    //    if(n%i==0)answer.push_back(i);
    for(int i=1;i<=sqrt(n);i++)
    {
        if(n%i==0)
        {
            answer.push_back(i);
        }
    }
    int s = answer.size();
    for(int i=s-1;i>=0;i--)
    {
        if(answer[i]!=n/answer[i])answer.push_back(n/answer[i]);
    }
    return answer;
}

 

설명

 

푸는 방식이 2가지가 있다. 

 

첫번째로 1부터 n까지 모든 수를 n%i 로 비교하는 것이다. 

for(int i=1;i<=n;i++)
        if(n%i==0)answer.push_back(i);

 

하지만 시간복잡도가 O(n) 이다.

 

두번째 방법은 루트 n까지만 비교해서 약수를 구하고 그 수를 바탕으로 짝을 이루는 약수를 찾는 것이다.

 

for(int i=1;i<=sqrt(n);i++)
    {
        if(n%i==0)
        {
            answer.push_back(i);
        }
    }
    int s = answer.size();
    for(int i=s-1;i>=0;i--)
    {
        if(answer[i]!=n/answer[i])answer.push_back(n/answer[i]);
    }

첫번째 for문을 보면 sqrt(n) 까지만 돈다. 

예를 들어, 100의 약수를 찾을 때, 굳이 100까지 확인하지 않고 10까지만 확인하면 그 뒤에 20같은 경우는 5의 짝이다.

따라서 루트 n까지만 확인하면 된다. 

 

두번째 for문을 통해서 지금까지 찾은 약수의 짝을 찾아서 대입한다.

위에서 찾은 10까지의 약수를 바탕으로 20, 50 ,100 을 대입하는 과정이다.

여기서 if문은 10이 중복되어 대입되는 것을 방지하기 위함이다.

이 방식은 O( log n ) 의 시간복잡도를 가지기 때문에 훨씬 효율적이라 할 만하다.