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

*문제

 

 

---

 

 

*풀이

class Solution {
    //최소공약수
    public static int gcd(int a, int b){
        while(b != 0){
        int temp = b;
        b = a % b;
        a = temp;
        } return a;
    }

    public static int[] solution(int numer1, int denom1, int numer2, int denom2) {
    int denom = denom1 * denom2;    //분모
    int numer = (numer1 * denom2) + (numer2 * denom1);  //분자
    int gcd = gcd(denom, numer);    //최소공약수
    //약분
    numer = numer/god;
    denom = denom/god;

    int[] answer = {numer, denom};

    return answer;
    }
}

• 소수 형태가 아닌 분수 형태가 필요 => 단순히 더하는 과정이 아님
• 분수의 덧셈
  • denom : 분모를 같은 수로 맞춰야 함 => 분모끼리 곱한다
  • numer : 분모에 곱한 수를 분자에도 곱해야 한다
  • gcd() 메서드 : 기약 분수로 만들기 위해 약분 과정을 거쳐야 한다. => 최대공약수가 필요함 
    • 최대공약수를 만드는 함수는 유클리드 호제법을 사용한다. 이 방법은 재귀적으로 GCD를 찾는 효율적인 알고리즘이다. 
      1. while (b != 0) :  b가 0이 될 때까지 반복
      2. temp : b 값을 임시로 저장
      3. b = a % b : 나머지 구하기
      4. a = temp : a를 b의 이전 값으로 갱신
      5. 이러한 과정을 b가 0이 될 때까지 반복
    • 이 때 a가 최대공약수이다. 즉, 최대공약수를 찾기 위해 계속해서 나머지를 구하면서 두 수를 계속 교환해 나가다가 나머지가 0이 되는 순간의 나누는 수가 최대공약수가 된다.

 

=> 최대공약수를 구하는 함수를 만드는 것에 어려움을 느껴 유클리드 호제법을 사용한 god()메서드를 참고함

 

 

 

 

---

 

 

 

✔️다른 풀이

class Solution {
    public int[] solution(int denum1, int num1, int denum2, int num2) {
        int mother = num1 * num2;	//분모
        int son = (num1 * denum2) + (num2 * denum1);	//분자
        // i는 1부터 mother 값까지 i--
        for(int i = mother; i >= 1; i--){
        	//만약 i값으로 분자와 분모를 나눴을 때 나머지가 0인 경우
            //즉, 분자와 분모 둘다 나누어 떨어지는 최소공약수가 i
            if(son % i == 0 && mother % i == 0){ 
                //최소공약수 i로 분모와 분자를 나누어준다.
                son /= i;	
                mother /= i;
            }
        }
        int[] answer = {son, mother};
        return answer;
    }
}

• 유클리드 호제법을 사용한 god() 메서드 없이 푼 풀이
• for문에서 최대공약수 i를 구함 
  • 1부터 분모 값 범위의 수를 분모와 분자 모두 나눠보며 나누어떨어질 때 그 수가 최대공약수가 된다.