[프로그래머스/java/Lv.0] 분수의 덧셈 (유클리드 호제법)

 

 

 

* 문제 풀이

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int[] answer = new int[2]; //배열 크기 2. 분자와 분모가 저장됨

        int num = denom1*denom2; //두 분모의 곱 저장
        int denom = numer1*denom2+numer2*denom1; //두 분수의 분자를 공통 분모로 맞추어 더한 값
        int max = 1; // 최대공약수는 1 이상의 자연수이기 때문에 초기값을 1로 설정

        for(int i=1; i<=num && i<= denom; i++){ // 최대공약수 찾기
            if(num%i==0 && denom%i==0){
                max = i; //max에 최대공약수가 저장됨
            }
        }
        answer[0]=denom/max; //분모
        answer[1]=num/max; //분자

        return answer;
    }
}

~>
기약분수 조건이 있어서 최소공배수를 구해야 한다.

 

* 풀이 참고 사이트
https://velog.io/@osohyun0224/프로그래머스-Lv.0-분수의-덧셈.java

 

 

※ 유클리드 호제법  (출처 위키백과)

2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나

두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘

** 자바 코드에서의 유클리드 호제법
public static int gcd(int p, int q)
 {
	if (q == 0) return p;
	return gcd(q, p%q);
 }

 

 

 

 

* 프로그래머스 다른 풀이

class Solution {
    public int[] solution(int denum1, int num1, int denum2, int num2) {
        int mother = num1 * num2;
        int son1 = num1 * denum2;
        int son2 = num2 * denum1;
        int totalSon = son1 + son2;
        for(int i = mother; i >= 1; i--){
            if(totalSon % i == 0 && mother % i == 0){
                totalSon /= i;
                mother /= i;
            }
        }
        int[] answer = {totalSon, mother};
        return answer;
    }
}