0-5. 소인수 분해 (set 컨테이너)

1. 문제

소인수분해란 어떤 수를 소수들의 곱으로 표현하는 것입니다. 예를 들어 12를 소인수 분해하면 2 * 2 * 3 으로 나타낼 수 있습니다. 따라서 12의 소인수는 2와 3입니다. 자연수 n이 매개변수로 주어질 때 n의 소인수를 오름차순으로 담은 배열을 return하도록 solution 함수를 완성해주세요.

---

제한사항

• 2 ≤ n ≤ 10,000

---

 

입출력 예

12	[2, 3]
17	[17]
420	[2, 3, 5, 7]

 

2. 코드

#include <string>
#include <vector>
#include <set>

using namespace std;

vector<int> solution(int n) {
    set<int> s;
    set<int>::iterator it = s.begin();
    vector<int> answer;

    for (int i = 2; i * i <= n; i++)
    {
        while (n % i == 0)
        {
            n /= i;
            s.insert(i);
        }
    }

    if (n != 1)
        s.insert(n);

    for (auto& num : s)
        answer.push_back(iter);



    return answer;
}

 

3. 분석

기본적으로 수를 소인수분해하는 방법은 for문과 while문의 중첩으로 해결할 수 있다.

다만 이 문제는 중복된 인수를 걸러내야 하므로 set 컨테이너를 사용한다.

 

(1) Set 연관 컨테이너

- 노드 기반의 균형 이진 트리

- 각 원소가 key에 해당 (<-> map에서는 key와 value의 두 값으로 이루어짐)

- 중복을 허용하지 않음 (map 또한 중복을 허용하지 않음)

- insert에 의해 삽입되면 자동으로 정렬 됨(오름차순)