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());
}
'자료구조 & 알고리즘 > 프로그래머스' 카테고리의 다른 글
Level 0. 가까운 수 (0) | 2023.02.02 |
---|---|
Level 0. 합성수 찾기 (0) | 2023.02.01 |
Level 0. 순서쌍의 개수 (1) | 2023.01.30 |
Level 0. 삼각형의 완성조건 (2) (0) | 2023.01.29 |
Level 0. OX퀴즈 (0) | 2023.01.28 |