프로그래머스 - 최대공약수와 최소공배수 C++

유클리드 호제법을 이용하면 쉽다. 아니 대놓고 이용하라는 문제인듯..

유클리드 호제법은 a와 b의 최대공약수는 b와 a mod b(=r)의 최대공약수와 같다는 건데,

이를 그대로 구현하여 b가 0이 될때까지 구해준다.

 

최소공배수는 이 a*b에 GCD(=최대공약수)를 구한 것을 나눠준 값이 된다.

 

아래는 재귀로 구현한 코드이다.

#include <string>
#include <vector>
 
using namespace std;
 
int GCD(int a, int b){
    if(b==0) return a;
    return GCD(b,a%b);
}
 
 
vector<int> solution(int n, int m) {
    vector<int> answer;
    
    if(n<m){
        int tmp = n;
        n=m;
        m=tmp;
    }
    answer.push_back(GCD(n,m));
    answer.push_back((n*m)/GCD(n,m));
    
    return answer;
}

아래는 while문을 이용한 방법이다.

return a를 해준다!

while문이 더 빠르긴 하다.

#include <string>
#include <vector>
 
using namespace std;
 
int GCD(int a, int b){
    while(b!=0){
        int r=a%b;
        a=b;
        b=r;
    }
    return a;
}
 
 
vector<int> solution(int n, int m) {
    vector<int> answer;
    
    if(n<m){
        int tmp = n;
        n=m;
        m=tmp;
    }
    answer.push_back(GCD(n,m));
    answer.push_back((n*m)/GCD(n,m));
    
    return answer;
}