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

체감 Level : ★★☆  Review: 최대공약수 알고리즘 , 기본적인 수학 지식 필요 최대공약수 알고리즘  = 유클리드 호제법을 활용을 하면 쉽게 풀 수 있다!

 

 

 💡분모 분자의 최대 공약수를 구하고, 각각 나눠주면 기약분수가 된다.

 

 💬 기약분수 ::  분모와 분자의 최대 공약수가 1인 분수를 말합니다. 

즉, 분수의 분자와 분모가 서로소인 상태, 더 이상 약분이 불가능한 상태를 의미

 

 💬 유클리드 알고리즘 !! 두 수의 나머지를 반복적으로 계산하여 GCD찾음

a를 𝑏 b로, 𝑏 b를 𝑟 r로 바꾸고, 𝑟 r이 0이 될 때까지 2번 과정을 반복

 

유클리드 알고리즘의 수식 유클리드 알고리즘의 핵심은 다음과 같은 수학적 성질에 기반합니다

GCD ( 𝑎 , 𝑏 ) = GCD ( 𝑏 , 𝑎 % 𝑏 ) 

GCD(a,b)=GCD(b,a%b) 여기서 % 는 나머지 연산자입니다.

 

//최대공약수(GCD, Greatest Common Divisor)는 
//두 개 이상의 정수의 공통된 약수 중 가장 큰 수

public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

 

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int[] answer = new int [2];
          //통분
        answer[0] = numer1 * denom2 + numer2 * denom1  ;
        answer[1] = denom1 * denom2 ;

 		//분수의 분자와 분모의 최대 공약수(GCD)
        int a =  answer[0] , b = answer[1];
       
        while (a != 0) {
            int temp = a;
            a = b % a;
            b = temp;
        }
        //분자와 분모를 최대 공약수로 나누어줍니다.
        answer[0] = answer[0] / b;
        answer[1] = answer[1] / b;
        
        //나눈 결과를 분자와 분모로 하는 분수가 기약분수
        return answer;
    }
}

 

 

 

[실패] 

테스트 케이스는 맞았지만 반례가 많았나보다...  거의 다 틀렸다 ㅠㅠㅠㅠ

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int[] answer = new int [2];
        
        
            if (denom1 == denom2){
                answer[0] = numer1 + numer2;
                answer[1] = denom1;
            }else if (denom2 % denom1 == 0){
                int tmp = denom1;
                denom1 *= denom2/denom1; 
                numer1 *= denom2/tmp;
                
            }else if(denom1 % denom2 == 0){
                denom2 *= denom1/denom2; 
                numer2 *= denom1/denom2; 
            }else {
              int tmp = denom2;
                denom2 *= denom1; numer2 *= denom1;
                denom1 *= tmp; numer1 *= tmp;
            }
               
            answer[0] = numer1 + numer2;
            answer[1] = denom1;
        
        return answer;
    }
}