[200513] 최대공약수와 최소공배수 - 연습문제(level1)

1. 문제이해

- 두 수를 입력받아 최대공약수와 최소공배수를 반환하기

 

2. 전략

(1) 둘 중 큰 수, 작은 수 판단하기 _ Math.min, Math.max 이용

(2) 작은 수의 약수들 구하기 _ 이전의 '약수의 합' 풀이법 이용

https://esw-csmoon.tistory.com/entry/200511-%EC%95%BD%EC%88%98%EC%9D%98-%ED%95%A9-%EC%97%B0%EC%8A%B5%EB%AC%B8%EC%A0%9Clevel1

[200511] 약수의 합 - 연습문제(level1)

(3) 마지막 index부터 시작해 큰수의 약수가 되는지 확인 후 최대공약수, 최소공배수 확정

    (최소공배수  = small * (big / gcd))

 

3. 참고사항

- 내 코드의 문제점 : 모든 약수를 다 구하고, 공통된 약수를 찾는 과정에서 시간복잡도 증가

- 다른 풀이 : 유클리드 호제법

(1) 유클리드 호제법이란?

: 두 양의 정수의 최대공약수를 구하는 오래된 알고리즘. 

두 양의 정수 a, b(a > b)에 대하여 a = bq + r (0<= r < a)라면, a,b의 최대공약수는 b, r의 최대공약수와 같다.
gcd(a, b) = gcd(b, r)
위 과정을 반복해 r이 0이 된다면 b값을 최대공약수라 할 수 있다!!

(출처 :https://namu.wiki/w/%EC%9C%A0%ED%81% B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95)

 

(2) GCD 코드

(단, a >= b인 값을 넣어줘야한다!!)

- 재귀함수

public int gcd(int a, int b){
    if(b==0)    return a;
    else{
        return gcd(b, a%b);
    }
}

- 반복문

public int gcd(int a, int b){
    int temp = 0;
    while(b!=0){
        temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

 

4. 코드

import java.util.*;
class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        int small = Math.min(n, m);
        int big = Math.max(n, m);
        /*//small의 약수들 구하기
        boolean[] sList = new boolean[small+1];
        for(int i = 1; i < Math.sqrt(small); i++){
            if(small % i == 0){
                sList[i] = true;
                sList[small/i] = true;
            }
        }
        //최대공약수, 최소공배수 구하기
        for(int i = sList.length-1; i >= 1; i--){
            if(sList[i] && big % i == 0){
                answer[0] = i;
                answer[1] = small * (big / i);
                break;
            }
        }*/
        answer[0] = gcd(big, small);
        answer[1] = big * small / answer[0];
        return answer;
    }
    
    public int gcd(int a, int b){
        if(b==0)    return a;
        else{
            return gcd(b, a%b);
        }
    }
}