프로그래머스 lvl 2. N개의 최소공배수 [C++]

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

 

제한 사항

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

 

접근 point

• 배열 오름차순 정렬
• 무식하게 접근

 

배열을 오름차순으로 정렬하게 되면, 가장 큰 수가 배열의 마지막에 위치하게 된다.

** 가장 큰 수는 배열의 나머지 수들의 최소공배수가 될 확률이 있기 때문에 오름차순으로 정렬하여 접근한다.

 

#include <bits/stdc++.h>
using namespace std;

int solution(vector<int> arr) {
    bool found = false;
    sort(arr.begin(), arr.end()); // 배열 오름차순 정렬
    int lcm = arr[arr.size()-1]; // 마지막 수를 최소공배수로 지정
    if(arr.size() > 1) {
        while(!found) {
            int idx = 0;
            while(idx < arr.size()-1) { 
                if(lcm % arr[idx] != 0) { // 최소공배수 여부 확인
                    found = false;
                    break;
                } else found = true;
                idx++;
            }
            // 아닐 경우, 다음 배수 확인
            if(!found) lcm += arr[arr.size()-1]; 
        }
    }
    return lcm;
}