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

🔗문제로 이동 👉 [분수의 덧셈]

이 문제의 핵심은 크게 아래와 같이 볼 수 있다.

• 최대공약수 / 최소공배수 구하기
• 유클리드 호제법 알고리즘 활용하기 (참고사이트)

☑️ 첫 번째 풀이

for문을 사용하여 최대공약수를 찾도록 코드를 짰다. 정답으로 인정은 됐지만 속도가 아쉬워 다시 풀어보았다.

class Solution {

    // 최대공약수
    public int gdc(int x, int y) {
        int min = 1;
        for(int i = 2; i <= Math.min(x, y); i++) {
            if(x%i == 0 && y%i == 0) {
                min = i;
            }
        }
        return min;
    }
    
    public int[] solution(int denum1, int num1, int denum2, int num2) {
        
        int num3  = (num1 * num2) / gdc(num1, num2); // 분자(최소공배수)
        int denum3 = (num3 / num1 * denum1) + (num3 / num2 * denum2); // 분모
        int result = gdc(num3, denum3); // 기약분수
        
        int[] answer = {denum3/result, num3/result};
        
        return answer;
    }
}

✅ 두 번째 풀이

그래서 알게된 유클리드 호제법! 위에 반복문을 돌리는 것 보다 가독성이 좋고 심지어 속도도 훨씬 빠르다. 이런 간단한 알고리즘은 외워두는게…

class Solution {

    // 최대공약수(유클리드 호제법)
    public int gdc(int x, int y) {
        if(x % y == 0) return y;
				return gdc(y, x % y);
    }
    
    public int[] solution(int denum1, int num1, int denum2, int num2) {
        
        int num3  = (num1 * num2) / gdc(num1, num2); // 분자(최소공배수)
        int denum3 = (num3 / num1 * denum1) + (num3 / num2 * denum2); // 분모
        int result = gdc(num3, denum3); // 기약분수
        
        int[] answer = {denum3/result, num3/result};
        
        return answer;
    }
}