programmers 최대공약수와 최소공배수

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

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

 

 

문제 분석

- 유클리드 호제법(https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95)을 통해 최대공약수를 구하였다.

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

- 최대공약수는 둘 중 큰 값을 작은 값으로 나누고 나머지를 큰 값을 담고있던 변수로, 나머지 값을 작은 값이 담고있던 변수로 채우며 while문을 반복한다.

- 최소공배수는 두 수를 곱하고 위에 구한 최대공약수로 나누어 계산한다.

- 최대공약수는 gcd라는 함수를 통해 값을 구하고 반환 받았다. 

 

 

문제 풀이

1. 큰 값과 작은 값을 구해 순서대로 gcd함수로 넘겨준다.

2. gcd함수에서는 유클리드 호제법(위의 분석 참고)을 통해 while문으로 최대공약수를 구한다.

3. 반환받은 최대공약수를 활용하여 최소공배수를 구한다.

4. 최소공배수는 초기의 값을 곱하고 구한 최대공약수로 나눈다.

 

import java.lang.Math;

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        
        int min = Math.min(n, m);
        int max = Math.max(n, m);
        
        answer[0] = gcd(max, min);
        answer[1] = n*m/answer[0];    
        return answer;
    }
    
    static int gcd(int a, int b){
        int temp = 0;
        while(true){
            if(b==0){
                break;
            }
            temp = a%b;
            a = b;
            b = temp;
        }
        return a;
    }
}

 

https://github.com/SOEUN2/Algorithm