Level 0. 약수 구하기

Level 0. 약수 구하기

 

 

1과 n은 무조건 포함되므로 생성 시 초기화해준다.

 

n까지 반복할 필요 없이 제곱근보다 작거나 같은 경우까지만 반복하고 제수(Divisor)와 몫(Quotient)을 함께 추가해줘도 된다.

 

vector에 삽입한 후 sort() 함수를 실행하면 O(nlog n) 복잡도를 갖게 된다.

 

애초에 레드-블랙 트리를 사용하여 정렬된 상태를 유지하는 set에 삽입하는 것 역시 O(nlog n)의 복잡도를 갖는다.

 

나는 코드 줄을 줄이고 이해하기 쉬운 코드를 짜기 위해 후자를 택했다.

 

#include <iostream>
#include <cmath>
#include <vector>
#include <set>

using namespace std;

vector<int> solution(int n)
{
    float square_root = sqrt(n);
    set<int> st = {1, n};

    for (int i = 2; i <= square_root; ++i)
        if ( (n % i) == 0 )
            st.insert({i, n / i});

    return vector<int>(st.begin(), st.end());
}