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

문제

최대공약수와 최소공배수 : 문제 링크

문제 분석

• 두 수를 입력받아 두 수의 최대공약수와 최소공배수를 return하는 함수, solution을 완성. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 return 하면 된다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 return 해야 한다.
• 제한 사항

  • 두 수는 1이상 1000000이하의 자연수이다.

• 유클리드 호제법에 따라 두 정수의 최대공약수를 구하는 함수 gcd를 초기화. if문을 통해 a를 b로 나눈 나머지가 0이라면 b를 return하고, 아니라면 else문을 통해 (b, a % b) 형태로 재귀. 두 정수의 최소공배수를 구하는 함수 lcm을 초기화. 최소공배수는 두 정수의 곱을 최대공약수로 나눠서 구할수 있으므로, 앞서 만든 함수 gcd를 활용.
• solution 함수에서는 최대공약수와 최소공배수를 저장할 정수형 벡터 answer을 초기화. gcd() 및 lcm() 함수로 구한 두 정수 n, m의 최대공약수 및 최소공배수를 각각 answer에 저장. 최종적으로 저장된 answer을 return

유클리드 호제법

• a, b가 정수이고 a >= b라고하고, a를 b로 나눈 나머지를 r이라고 한다. 이때 a와 b의 최대공약수를 (a, b)라고 하면 (a, b) = (b, r)이 성립한다.

풀이

#include <vector>

using namespace std;

int gcd(int a, int b) {
    if(a % b == 0) return b;
    else return gcd(b, a % b);
}

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

vector<int> solution(int n, int m) {
    vector<int> answer;
    
    answer.push_back(gcd(n, m));
    answer.push_back(lcm(n, m));
    return answer;
}