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

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

using namespace std;

int solution(vector<int> arr) {
    int gcd = *min_element(arr.begin(), arr.end());
    int flag = 0;
    int j;
    
    for(; gcd >= 1 ; gcd--){
        flag = 0;
        for(j = 0; j < arr.size(); j++){
            if(arr[j] % gcd == 0) flag = 0;
            if(arr[j] % gcd != 0){
                flag = 1;
                break;
            }
        }
        if(flag == 0) break;
    }
    
    int answer = gcd;
    for(j = 0; j < arr.size(); j++){
        answer = answer * (arr[j]/gcd);
    }
    
    return answer;
}

gcd가 arr 배열에서 제일 작은 값 부터 시작해서  배열의 모든 값들이 gcd 로 나누어 떨어질 때 까지 gcd--해서 최대 공약수를 구하고, 최소공배수는 gcd * ( 모든 배열 값 / gcd ) 이라고 생각하고 코드를 작성했는데

자꾸 실패만 뜬다. 그래서 다른 사람들 코드를 봤는데 , 다들 최대공약수를 배열에서 두 개씩 꺼내서 구한다.

진짜 왜 그러지 도저히 이해되지 않았는데 다음과 같은 예시를 생각하면 '아...!!!!!!!!!' 라고 깨닫게 된다.

 

 

 

arr = [2, 6, 8, 24] 인 경우

내 방식대로 하면 최대공약수는 2이고 최소공배수는 2 * ( 1 * 3 * 4 * 12) = 288이 된다.

하지만 2개씩 뽑는 방식으로 하면 2 와 6의 최소공배수 6, 8과 24의 최소공배수 24. 

다시 6, 24의 최소공배수를 구하면 24가 된다.

 

2개씩 뽑고 최소공배수를 구해서 다시 넣기 위해 큐를 사용했다.

#include <queue>
using namespace std;

int get_lcm(int a, int b){
    int gcd = a>b? b:a;
    for(; gcd >0; gcd--){
        if(a%gcd==0 && b%gcd==0){
            break;
        }
    }
    return gcd*(a/gcd)*(b/gcd);
}

int solution(vector<int> arr) {
    queue<int> lcm;
    for(int i =0; i<arr.size(); i++) lcm.push(arr[i]);
    
    while(lcm.size() != 1){
        int first = lcm.front();
        lcm.pop();
        int second = lcm.front();
        lcm.pop();
        lcm.push(get_lcm(first, second));
    }
    return lcm.front();
}