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

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

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

 

1. 서론

 

생각나는 대로 풀면 맞는 level 1문제. 최대공약수와 최소공배수라는 단어를 너무 오랜만에 들어서 살짝 당황하긴 했지만 쉽다.

 

2. 문제 풀이

 

두 수가 주어진다. 그 두 수의 최대공약수와 최소공배수를 구해서 배열로 만들어 return 하는 문제이다.

 

3 | 3 12

   -------

     1   4

 

최대 공약수 : 3

최소 공배수: 3 * 1 * 4 = 12

 

중학생때 쯤 배웠던 바로 그 개념! 종이에 적어보니 바로 생각이 났다. 그래서 저 계산을 바로 공식화했다.

 

1. 두 수 모두의 나머지가 0이게 만드는 수 구하기

2. 그 수와의 약수를 구해서 곱하기

3. 곱해서 구한 공배수끼리 비교해서 더 작은 수가 나오면 값을 바꿔서 넣어주기

 

3. 코드 설명

 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, int m) {
    vector<int> answer;
    int i, x, c;
    
    x = max(n, m);
    
    for (i = 1; i <= x; i++)
    {
        if (n % i == 0 && m % i == 0)
        {
            c = 1;
            c *= i;
            c *= n / i;
            c *= m / i;
            
            if (!answer.empty())
            {
                if (c < answer[1])
                {
                    answer.pop_back();
                    answer.pop_back();
                }
            }
            answer.push_back(i);
            answer.push_back(c);
                
        }
    }
    
    return answer;
}

 

1부터 두 수 n, m 중 더 큰 수까지 for문을 돌려준다. 

그 안에서 둘 다 나머지가 0인, 즉 둘 다 나눌 수 있는 값이 나올 때 c에다가 공배수를 구해준다.

그리고 배열에 비어있다면 그냥 값을 넣고 아니라면 공배수의 크기를 비교해서 값을 바꿔준다.