Lv.1 최대공약수와 최소공배수

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

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

기본틀

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = {};
        return answer;
    }
}

첫번째 시도

class Solution {
    public int[] solution(int n, int m) {
        int gcd = 0, lcm = 0;
        int a = 0, b = 0, r = 1;
        
        if(n > m){
            a = n;
            b = m;
        } else{
            a = m;
            b = n;
        }
        while(r != 0){
                r = a % b;
                a = b;
                b = r;
        }
        gcd = a;
        lcm = n * m / gcd;
        
        
        int[] answer = {gcd, lcm};
        return answer;
    }
}

성공!

 

* 이 문제를 풀기 위해 구글링을 조금 했다 ↓

1. 유클리드 호제법

두 개의 자연수 a, b (a>b) 에 대해 a 를 b 로 나눈 나머지가 r일 때, a 와 b 의 최대공약수는 b 와 r 의 최대공약수와 같다

2. 최소공배수는 두 수를 곱하고 이를 두 수의 최대공약수로 나눈 값이다