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

https://programmers.co.kr/learn/courses/30/lessons/12953

코딩테스트 연습 - N개의 최소공배수

여러수의 최소공배수를 구하는 문제입니다.

 

여러 수를 나열해두고, 두개 이상이 나눠진다면 나눠지는 수들만 나누고 나누어지지 않는다면 증가시키는 방법으로 풀었습니다.

 

예를 들어서,  [2, 4, 6, 8, 9] 가 있다면

2로 나누면    [1, 2, 3, 4, 9] 가 되고, 여기서 2로 한번 더 나누어지므로

2로 나누면    [1, 1, 3, 2, 9] 가 됩니다. 이제는 2로는 안 나누어지므로 증가시켜서 3으로 나누어야 합니다.

3으로 나누면 [1, 1, 1, 2, 3] 이 됩니다. 이제는 더이상 나누어지지 않으므로,

 

(2 * 2 * 3) * (1 * 1 * 1 * 2 * 3) = 72가 최소공배수가 됩니다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> arr) {
    int answer = 1;
    int len = arr.size();   // 원소의 개수
    int div = 2;
    int divcount = 0;       // 나눠지는 개수
    
    sort(arr.begin(), arr.end());   // 정렬
    int big = arr[len-1];   // 가장 큰 수
    
    while(div <= big)       // 가장 큰 수보다 나누는 수가 커질 수는 없음
    {
        for(int i=0; i<len; i++)
        {
            if(arr[i] % div == 0)
            {
                divcount++;     // 나눠지는지 안나눠지는지 확인
            }
        }
        
        if(divcount > 1)        // 두개이상 나눠진다면
        {
            for(int j=0; j<len; j++)
            {
                if(arr[j] % div == 0)
                {
                    arr[j] = arr[j] / div;  // 수를 나눔
                }   
            }
            divcount = 0;           // 다시 계산
            answer = answer * div;  
        }
        else
        {
            div++;
            divcount = 0;
        }
    }
    
    for(int k=0; k<len; k++)
    {
        answer = answer * arr[k];   // 마지막으로 남은 수를 구함
    }
    
    return answer;
}