[프로그래머스 / C++] 소인수분해

문제

소인수분해 : 문제 링크

문제 분석

• 자연수 n이 매개변수로 주어질 때 n의 소인수를 오름차순으로 담은 배열을 return
• answer 벡터에 저장되는 소인수가 겹치지 않도록, find 함수를 사용할 것이므로 algorithm 헤더를 include
• 인덱스는 2로 시작하고, n은 그것의 제곱보다 큰 수가 될수 없다는 성질을 활용하여 제곱값까지 for문이 작동한다.
• n을 인덱스로 나눈 나머지가 0이라면, 즉 인수로 분해가 된다면 그 인덱스는 소인수이므로 배열에 저장해야한다. find 명령어를 사용하여 answer 벡터내에 그값이 있는지 확인 후 없다면 값을 저장한다. 그 후 n을 인덱스로 나눈 몫으로 저장한다.
• 주어진 n 자체가 소인수인 경우도 있으므로, for문을 모두 통과한 후 n값이 1보다 클경우 n값을 벡터에 저장한다.

1. vector내에 해당 원소가 존재하는지 확인
=> find(v.begin(), v.end(), 찾을 대상)
1) return 값이 v.end()인 경우 => 해당 원소가 존재하지 않음
2) return 값이 v.end()가 아닌 경우 => 해당 원소가 존재함
2. vector내에서 해당 원소가 위치하는 인덱스 찾기
=> find(v.begin(), v.end(), 찾을 대상) - v.begin

풀이

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(int n) {
    vector<int> answer;
    for(int i = 2; i * i <= n; i++) {
        while(n % i == 0) {
            if(find(answer.begin(), answer.end(), i) == answer.end()) answer.push_back(i);
            n /= i;
        }
    }
    if(n > 1) answer.push_back(n);
    
    return answer;
}