codewars: Sum by Factors

문제 링크입니다: http://www.codewars.com/kata/54d496788776e49e6b00052f/train/cpp

소인수분해를 할 때 주어진 숫자를 절대값을 취해주지 않아 헤맸던 문제였습니다.

/*

양수와 음수로 채워진 벡터가 있다.

다음과 같은 양식으로 결과를 출력해야한다.

(소수, 해당 소수로 나누어지는 숫자들의 합) ...

*/

#include <iostream>

#include <string>

#include <vector>

#include <set>

#include <queue>

#include <algorithm>

using namespace std;

 

class SumOfDivided

{

public:

        static std::string sumOfDivided(std::vector<int> &lst);

};

 

vector<int> prime; //소수

set<int> used; //이미 포함된 소수인가?

 

void getPrimeNum(vector<int> &lst) //소인수 분해를 통해 소수를 찾는다

{

        vector<int> copy = lst;

        for (int i = 0; i < copy.size(); i++)

               for (int j = 2; j <= abs(copy[i]); j++) //abs(copy[i]) 중요!!!!!

                       while (copy[i] % j == 0)

                       {

                              if (!used.count(j)) //이미 찾은 소수면 벡터에 추가하지 않는다

                              {

                                      prime.push_back(j);

                                      used.insert(j);

                              }

                              copy[i] /= j;

                       }

}

 

string SumOfDivided::sumOfDivided(vector<int> &lst)

{

        queue<pair<int, int>> q; //해당 소수, 합

        string result; //결과

 

        getPrimeNum(lst); //소수를 찾고

        sort(prime.begin(), prime.end()); //소수를 정렬

 

        for (int i = 0; i < prime.size(); i++)

        {

               int sum = 0;

               for (int j = 0; j < lst.size(); j++)

                       if (abs(lst[j]) % prime[i] == 0) //나누어떨어질 경우

                              sum += lst[j];

               q.push(pair<int, int>(prime[i], sum)); //소수와 합 queue에 추가

        }

        while (!q.empty())

        {

               pair<int, int> current = q.front();

               int primeNum = current.first;

               int total = current.second;

               q.pop();

               if (total) //합이 0이면 출력하지 않는다

               {

                       result += "(";

                       result += to_string(primeNum);

                       result += " ";

                       result += to_string(total);

                       result += ")";

               }

        }

        return result;

}

int main(void)

{

        vector<int> d1 = { 12, 15 };

        cout << SumOfDivided::sumOfDivided(d1) << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~