[프로그래머스/JAVA] 분수의 덧셈(최대공약수 - 유클리드 호제)

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int[] answer = new int[2];
        
        int denum3 = denom1 * denom2;
        int num3 = numer1*denom2 + numer2*denom1;
        int gcd = getGCD(denum3, num3);
        
        answer[0] = num3/gcd;
        answer[1] = denum3/gcd;
        
        return answer;
    }
    
    public static int getGCD(int num1, int num2){
        if(num1%num2 == 0){
            return num2;
        }
        return getGCD(num2, num1%num2);
    }
}

유클리드 호제법 (최대공약수 구하기)

a % b = r 이라면

a와 b 의 최대공약수와 b와 r의 최대공약수는 같다.

 

➡ b % r = r' 라면

b와 r의 최대공약수는 r과 r'의 최대공약수와 같다.

 

➡나머지가 0이 될 때, 나눈 수가 a와 b의 최대공약수가 된다.

 

package com.company;

public class Main {

    public static void main(String[] args) throws Exception {
        int n1 = 12;
        int n2 = 8;

        int gcd = getGCD(n1, n2);
        System.out.println("gcd = "+gcd);

    }

    public static int getGCD(int num1, int num2){
        if(num1 % num2 == 0){
            return num2;
        }
        return getGCD(num2, num1%num2);
    }
}

 

---

다른 풀이

for문으로 최대공약수 찾기

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int[] answer = new int[2];
        
        int denum3 = denom1 * denom2;
        int num3 = numer1*denom2 + numer2*denom1;
        int max = 1;
        
        // 최대 공약수
        for(int i=1; i<=num3 && i<=denum3; i++){
            if(num3%i==0 && denum3%i==0){
                max = i;
            }
        }
        answer[0] = num3/max;
        answer[1] = denum3/max;
        
        return answer;
    }
}