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

문제 설명

첫 번째 분수의 분자와 분모를 뜻하는 numer1, denom1, 두 번째 분수의 분자와 분모를 뜻하는 numer2, denom2가 매개변수로 주어집니다. 

두 분수를 더한 값을 기약 분수로 나타냈을 때 분자와 분모를 순서대로 담은 배열을 return 하도록 solution 함수를 완성해보세요.

제한사항

- 0 <numer1, denom1, numer2, denom2 < 1,000

입출력 예 설명

입출력 예 #1
1 / 2 + 3 / 4 = 5 / 4입니다. 따라서 [5, 4]를 return 합니다.

입출력 예 #2
9 / 2 + 1 / 3 = 29 / 6입니다. 따라서 [29, 6]을 return 합니다.

제출코드 

1. 각자 다른 분모를 가진 두 분수를 더하려면 통분 작업을 통해 분모를 통일하고 분수를 더합니다.
   - 분자 = 각 분자에 상대 분수의 분모를 곱하고 더한 값 (a/b, c/d = a*d + c*b)
   - 분모 = 각 분모의 곱 (a/b, c/d = b*d)
2. 이렇게 더한 분수에 유클리드 호제법(Euclidean Algorithm)을 사용하여 최대공약수를 구하고 각 분자와 분모를 나누어 줍니다.
   - 분자 = 분자 / 최대공약수
   - 분모 = 분모 / 최대공약수

통분(reduction to common denominator)

수학에서 분모가 다른 2개 이상의 분수의 분모를 같게 하는 작업을 말한다. 

유클리드 호제법(Euclidean Algorithm)

2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 

호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 

이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 

class Solution {
    
    public boolean valid(int number) {
        return 0 < number && number < 1000;
    }
    
    public int gcd(int numer, int denom) {
        while (denom != 0) {
            int remainder = numer % denom;
            numer = denom;
            denom = remainder;
        }    
        return numer;
    }
    
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int[] answer = {};
        if (valid(numer1) && valid(denom1) && valid(numer2) && valid(denom2)) {
            int numer = (numer1 * denom2) + (numer2 * denom1);
            int denom = denom1 * denom2;    
            
            int max = gcd(numer, denom);
            numer /= max;
            denom /= max;
            
            answer = new int[] { numer, denom };
        }
        return answer;
    }
}

 

---

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

프로그래머스