[level 1] 최대공약수와 최소공배수

문제 설명

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

제한 사항

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

문제 이해

입력받은 두 수 n과 m의 최대공약수와 최소공배수를 구해서 answer벡터에 넣어 반환해야한다.

최대공약수는 유클리드 호제법을 사용해서 구하고 최소공배수는 n과 m을 곱한 후 최대공약수로 나누어주면 구할 수 있다.

 

알고리즘

유클리드 호제법 알고리즘
 1. 입력으로 두 수 m,n(m>n)이 들어온다.
 2. n이 0이라면, m을 출력하고 알고리즘을 종료한다.
 3. m이 n으로 나누어 떨어지면, n을 출력하고 알고리즘을 종료한다.
 4. 그렇지 않으면, m을 n으로 나눈 나머지를 새롭게 m에 대입하고, m과 n을 바꾸고 3번으로 돌아온다.

최대공약수를 구한 후 두 수를 곱하고 최대공약수로 나누어 최소공배수를 구한다.

 

풀이 코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, int m) {
    vector<int> answer;
    int a = n, b = m;
    int lcm = 0;

    for (int i = 0; true; i++) { // 유클리드 호제법 (최대공약수)
        if (a % b == 0 || b % a == 0) { 
            if (a < b) {answer.push_back(a); }
            else { answer.push_back(b); }
            break; 
        }
        else {
            if (i % 2 == 0) { a = a % b; }
            else { b = b % a; }
        }
    }

    answer.push_back(n * m / answer[0]); // 최소공배수

    return answer;
}

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

프로그래머스