[프로그래머스] "최대공약수와 최소공배수" (Java)

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

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

---

유클리드 호제법을 알면 쉽게 풀 수 있는 문제입니다. 알고리즘이 정해져 있는 문제는 특정 알고리즘을 아예 외우는 것도 방법이라고 생각합니다.

http://lonpeach.com/2017/11/12/Euclidean-algorithm/

 

 

- void solution(int n, int m)

파라미터는 입력 받고, 입력 받은 두 수를 큰 수는 big, 작은 수는 small에 넣어줍니다. 그리고 gcd()메소드를 호출하고 그에 따라 최대공약수, 최소공배수를 구합니다. 최소공배수는 주어진 두 수를 곱하고 최대 공약수를 나누면 됩니다.

 

- int gdc(int big, int small) 

최대공약수를 더하는 메소드입니다. 간단하게 설명하자면, big을 small로 나눕니다. 나누어 떨어지면 small이 최대공약수 이고 나누어 떨어지지 않으면 재귀 호출을 통해 기존 small 값을 big에 넣고, small자리에는 big%small 연산 결과 값이 들어갑니다.

 

코드

import java.util.*;

public class solution {

    public int[] solution(int n, int m) {  
        int[] answer = new int[2];
        
        int big = 0, small =0; // 2) 큰 수, 작은 수를 나눠주기 위한 변수 생성.
        
        if(n>m) { // 3) 둘 중에 큰수를 big, 작은 수를 small에 저장해주자.
        	big = n; 
        	small = m;
        } else {
        	big = m;
        	small = n;
        }
        
        answer[0] = gcd(big, small); // 최대공약수
        answer[1] = big*small / answer[0]; // 최소공배수
        
        
        return answer;
    }
    // 유클리드 호제법을 이용한 최대공약수이다.
    public int gcd(int big, int small) { 
    	
        if(big % small == 0) { // 만약 나누어 떨어지면 small이 최대공약수가 된다.
    		return small;
    	} 
        
        // 7) 나누어 떨어지지 않으면 small이 big 자리에 가고 small자리에는 big을 small로 나눈 나머지 값이 온다.
    	return gcd(small, big%small);
    }
}

※  피드백 얼마든지 환영합니다.