[2025.01.09] 최대공약수와 최소공배수

문제 설명

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

 

 

제한사항

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

 

 

입출력 예

n			m	return	설명
3			12	[3, 12]	위의 설명과 같습니다.
2			5	[1, 10]	자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

 

 

문제 풀이

풀이 언어 : C++

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, int m) {
    vector<int> answer;
    vector<int> common_divisors; //나누어지는 divisor 모음
    
    int number_of_repetitions=0; // 반복 횟수
    if(n<=m) number_of_repetitions=n+1; // m과 n중 더 작은 수로 설정
    else number_of_repetitions=m+1;
    
    // 공약수 구하기
    for(int divisor=2; divisor<number_of_repetitions; divisor++)
    {
        // 공약수라면
        if(n%divisor==0&&m%divisor==0)
        {
            common_divisors.push_back(divisor); // result_divisor에 저장
            
            // n, m 업데이트
            n/=divisor;
            m/=divisor;
            
            // divisor 업데이트
            divisor-=1; // (같은 수로 또 나눠질 수도 있기 때문에)
        }
    }
    
    // 1 말고는 공약수가 없는 경우
    if(common_divisors.size()==0)
    {
        answer.push_back(1); // 최대공약수 1
        answer.push_back(m*n); // 최소공배수 n*m
    }
    else
    {
        // 최대 공약수
        int greatest_common_divisor=1;
        for(int i=0; i<common_divisors.size(); i++)
        {
            greatest_common_divisor*=common_divisors[i]; // 모든 공약수들 곱하기
        }
        answer.push_back(greatest_common_divisor);
        
        // 최소 공배수
        int least_common_multiple=greatest_common_divisor*n*m; // 모든 공약수와 나머지들 곱하기
        answer.push_back(least_common_multiple);
    }
    return answer;
}

최대공약수와 최소공배수를 구하는게 너무 오래만이라 구하는 방법을 찾아봤다. 그리고 아래의 계산을 그대로 코드로 구현해보려고 한다. 저렇게 나누면 최대공약수와 최소공배수를 모두 구할 수 있다. 최대공약수는 왼쪽의 두 수를 곱한 6(2*3)이다. 그리고 최소공배수는 왼쪽 두 수와 아래 두 수를 곱한 210(2*3*5*7)이다. 따라서 왼쪽의 두 수와 아래의 두 수를 구하면 되는 것이다.

왼쪽의 수, 즉 공약수를 저장할 벡터 common_divisors를 정의한다. 그리고 반복 횟수를 정하기 위해 number_of_repetitions을 정의한다. 반복 횟수는 n과 m중 작은 수에 +1을 한 것으로 한다. 공약수가 될 수 있는 수는 아무리 커도 n과 m 둘 중 작은 수까지일 것이기 때문이다.

 

반복문을 돌며 1을 제외한 공약수를 모두 구해서 common_divisors에 저정한다. 1을 제외해야하기 때문에 반복문은 2부터 시작한다. 반복문을 돌며 n과 m이 모두 divisor로 나누어 떨어지는 경우 공약수로 저장한다. 그리고 n과 m을 divisor로 나눈 수로 업데이트한다. 위 그림에서는 15와 21로 만들어주었다고 생각하면 된다. 그리고 divisor를 -1한다. 왜냐하면 다시 똑같은 divisor로 나눠질 수도 있기 때문이다. 12와 16을 예로 들면 2로 나누면 각각 6과 8로 나누어 떨어지지만 2로 한번 더 나눌 수 있기 때문이다. 그래서 divisor-1을 하고 반복문이 돌아갔을 때 divisor++를 하여 같은 divisor 값으로 한번 더 나눠지는지 확인한다. 반복문이 number_of_repetitions만큼 전부 다 돌아가서 빠져나왔다는 것은 더이상 공약수가 없다는 뜻이다.

 

모든 공약수를 구했다면 이제 최대공약수와 최소공배수를 구해야 한다. 먼저 공약수가 전혀 없는 경우 부터 answer를 설정해준다. 만약 common_divisors의 원소의 개수가 0이라면 최대공약수는 1, 최소공배수는 n*m을 뜻한다. 따라서 answer에 그 값들을 push_back 해준다.

 

만약 원소가 존재한다면 최대공약수와 최소공배수를 구해주면 된다. 최대 공약수는 common_divisors에 있는 모든 원소의 곱이다. 그래서 반복문을 돌며 모든 원소를 곱해준다. 그리고 answer에 삽입한다. 최소 공배수는 common_divisors에 있는 모든 원소의 곱에 n과 m을 곱하면 된다. 위에 그림으로 치면 n과 m은 각각 5, 7인 상태이다. 이렇게 최소 공배수를 모두 계산한 후 answer에 삽입한다. 마지막으로 answer을 리턴해준다.

 

오답 노트

반복문이 돌아가는 횟수를 잘못 생각했다. 반복문은 n과 m중 작은 수만큼 돌아야 하는데 잘못해서 2~9까지만 돌도록 하였다. 왜 갑자기 이런 생각을 하고 코드를 짰는지는 나도 잘 모르겠다.

for(int divisor=2; divisor<=10; divisor++)
{
    if(n%divisor==0&&m%divisor==0)
    {
        result_divisor.push_back(divisor);
        n/=divisor;
        m/=divisor;
        divisor-=1;
    }
}

 

 

문제 링크

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

프로그래머스