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

📝 N개의 최소공배수

문제 설명

N개의 최소공배수

해결 방법

유클리드 호제법 알고리즘 O(log a)을 이용하여 최대공약수를 구한다. 두 수의 최소공배수는 두 수의 곱을 최대공약수로 나눈 값이다. a * b / gcd(a, b)
두 수의 최소공배수를 구하고, 그 수와 다음 수의 최소공배수를 구하는 방식으로 하면 N개 수의 최소공배수를 구할 수 있다. 두 수를 pop한 뒤 두 수의 최소공배수를 push_back 하면서 배열 크기가 1이 될때까지 반복하면 arr[0]에 남아있는 수가 N개 수의 최소공배수이다.

💻소스코드

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

using namespace std;

// 유클리드 호제 a > b
int gcd(int a, int b) {
    int r = 0;
    while (b) {
            r = a % b;
            a = b;
            b = r;
    }
    return a;
}

int solution(vector<int> arr) {
    while (arr.size() != 1) {
        int i = arr.size() - 1;
        int x = arr[i];
        int y = arr[i - 1];
        arr.pop_back();
        arr.pop_back();
        arr.push_back((x * y) / gcd(x, y));
    } 
    return arr[0];
}