[프로그래머스 / Java] 분수의 덧셈

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/120808

문제 풀이

1. 유클리드 호제법이 생각나지 않아서 생각나는 대로 품.

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int[] answer = {};
        int num = numer1 * denom2 + numer2 * denom1;
        int den = denom1 * denom2;
        int minVal = Math.min(num, den);
        
        int i = 1;
        while (i <= minVal) {
            if (num % i == 0 && den % i == 0) {
                num /= i;
                den /= i;
                i = 1;
            }
            i++;
        }
        return new int[] {num, den};
    }
}

• i 를 1로 초기화 하지 않으면 12/8 에서 엣지 케이스를 처리할 수 없음.

 

2. 최대 공약수를 구한다면, 1번 방법과 같이 i 를 1부터 증가시킬 필요가 없음.

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int[] answer = {};
        int num = numer1 * denom2 + numer2 * denom1;
        int den = denom1 * denom2;
        int minVal = Math.min(num, den);
        
        for (int i = minVal; i > 0; i--) {
            if (num % i == 0 && den % i == 0) {
                num /= i;
                den /= i;
            }
        }
        return new int[] {num, den};
    }
}

 

3. 유클리드 호제법 쓰면 편함

class Solution {
    public int[] solution(int denum1, int num1, int denum2, int num2) {
        int num = denum1 * num2 + denum2 * num1;
        int denum = num1 * num2;
        int gcd = gcd(num, denum);
        return new int[] {num / gcd, denum / gcd};
    }

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

• 유클리드 호제법 : 양의 정수 a, b (a>b) 에서 a 를  b로 나눈 나머지를 r 이라고 할때, GCD(a, b) = GCD(b, r) 을 기반으로 함.
  • 나머지가 0이 될때의 b 값이 두 수의 최대공약수가 됨.