[프로그래머스] N개의 최소 공배수 c++

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12953?language=cpp 

프로그래머스

 

문제

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

제한 사항

• arr은 길이 1이상, 15이하인 배열입니다.
• arr의 원소는 100 이하인 자연수입니다.

입출력 예

arr	result
[2,6,8,14]	168
[1,2,3]	6

 

코드 및 풀이

/*

N개의 최소 공배수

일단 소수라면? -> 그냥 곱하면 되지 않을까? 근데 소수 , 소수 *n을 비교할 수도 있음

그럼 2이상의 숫자에서 같이 나눠지는것은 다 나누는 행위?

100이하니 100까지 가면서 혹은 2부터 max인 친구까지 가면서 그 숫자까지 일단 나눠지는 것이 두개 이상이 있다면 나눔

*/

#include <string>

#include <vector>

#include <cstring>

#include <algorithm>

#include <iostream>

using namespace std;

int solution(vector<int> arr) {

    int answer = 1;

    int div_arr[15];

   

    int max_num = *max_element(arr.begin(),arr.end());

    int i = 2;

    while(i <= max_num){

        int div_cnt = 0; // cnt -> 나눠지게 되면 cnt++을 진행해 2개 이상 체크

        memset(div_arr,0,sizeof(div_arr));

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

            if(arr[j] % i == 0){

                div_cnt++;

                div_arr[j] = 1;

            }

        }

        if(div_cnt >= 2){

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

                if(div_arr[j] == 1)

                    arr[j] /= i;

            }

            answer *= i;

            i = 1;

            max_num = *max_element(arr.begin(),arr.end());

        }

        i++;

    }

   

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

        answer *= arr[i];

    }

   

    return answer;

}