분수의 덧셈 (최대공약수 코드공식 암기할것)

문제

내풀이

class Solution {
    public int[] solution(int number1, int denom1, int number2, int denom2) {
        int lastNum = (number1*denom2)+(number2*denom1);

        int lastDenom = denom1*denom2;

        System.out.println("lastNum = " + lastNum);
        System.out.println("latDenom = " + lastDenom);

        int val = gcd(lastNum,lastDenom);

        int[] answer = new int[]{lastNum/val, lastDenom/val};
        
        return answer;
    }
    
    public static int gcd(int lastNum, int lastDenom){
        if(lastDenom == 0) return lastNum;
        
        return gcd(lastDenom, lastNum%lastDenom);
    }
}

풀이법

이 문제는 최종적으로 분자와 분모의 공통의 최대공약수로 나누는 것이 관건이다. 그러므로 최대공약수 공식 코드를 외우고 있어야 풀기 편하다

최대공약수(GCD, Greatest Common Divisor)란?
두 개 이상의 수에서 공통된 약수 중 가장 큰 값을 의미합니다.

예제 : 24와 36의 최대공약수 구하기

• 24의 약수: 1, 2, 3, 4, 6, 8, 12, 24
• 36의 약수: 1, 2, 3, 4, 6, 9, 12, 18, 36
• 공통된 약수: 1, 2, 3, 4, 6, 12
• 최대공약수(GCD) = 12

유클리드 호제법을 이용한 최대공약수 구하기

최대공약수는 유클리드 호제법을 이용하여 구할 수 있는데, 이는 큰 수를 작은 수로 나눈 나머지를 반복적으로 취하여 나머지가 0이 될 때 까지 작동하여 구하는 방식이다.

최대공약수 구하는 아래코드 반드시 암기!!!!!!!!!!!

// 재귀 방식
public static int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}