[프로그래머스] 최대공약수와 최소공배수

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

코딩테스트 연습 - 최대공약수와 최소공배수

---

 

-풀이-

gcd알고리즘을 이용하여 최대공약수를 구한다. 그다음 n*m/gcd = 최소공배수를 이용하여 최소공배수도 구한다.

 

-시간복잡도-

모든 로직이 단순 계산이기때문에 O(1)이 된다.

 

-코드-

#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 temp=n;
        n=m;
        m=temp;
    }
    
    int _gcd=gcd(n,m);
    
    answer.push_back(_gcd);
    answer.push_back(n*m/_gcd);
    
    return answer;
}