[C# 문제풀이 2일차] 분수의 덧셈 뺄셈

문제 설명
첫 번째 분수의 분자와 분모를 뜻하는 numer1, denom1, 두 번째 분수의 분자와 분모를 뜻하는 numer2, denom2가 매개변수로 주어집니다. 두 분수를 더한 값을 기약 분수로 나타냈을 때 분자와 분모를 순서대로 담은 배열을 return 하도록 solution 함수를 완성해보세요.

제한사항
0 <numer1, denom1, numer2, denom2 < 1,000

 

입출력 예
numer1 denom1 numer2 denom2 result
1 2 3 4 [5, 4]
9 2 1 3 [29, 6]
입출력 예 설명
입출력 예 #1

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

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

---

풀이

• Step1 ) 위 문제를 해결하기 위해선 최대공약수, 최소 공배수를 찾는 함수가 필요하다

1) 최대 공약수를 찾는 함수

최대 공약수의 경우 유클리드 호제법을 이용하여 찾는다.

 

• 유클리드 호제법:
  • 두 수 a와 b가 있을 때, a % b의 나머지가 0이 될 때까지 반복적으로 나누기를 수행합니다.
  • b가 0이 되면 a의 값이 최대공약수입니다.

 

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

 

2) 최소 공배수를 찾는 함수

두 수 A와 B를 곱한 값을 최대 공약수로 나눈 값이 최소 공배수이다.

public int LCM(int a, int b)
{
    int result = (a * b) / GCD(a, b);
    return result;
}

 

 

• Step2 ) 두 수의 최소공배수를 분모로 갖는 값으로 치환하여 두 분수의 합을 계산해준다.
• Step3 ) 계산한 분수의 분자,분모의 최대공약수를 찾아 약분해준다.

    public int[] solution(int numer1, int denom1, int numer2, int denom2) 
    {
        int[] answer = new int[2];
        
        if(denom1%denom2 == 0)
        {
            int a = numer1;
            int b = denom1;
            int c = numer2 * (denom1/denom2);
            
            int newNumer = a + c;
            
            //두 수의 최대공약수 구하기
            if(GCD(newNumer, denom1) == 1)
            {
                answer[0] = newNumer;
                answer[1] = denom1;
            }
            else{
                answer[0] = newNumer/GCD(newNumer, denom1);
                answer[1] = denom1/GCD(newNumer, denom1);
            }
            
        }
        else if(denom2%denom1 == 0)
        {
            int a = numer1 * (denom2/denom1);
            int b = denom2;
            int c = numer2;
            
            int newNumer = a + c;
            
            //두 수의 최대공약수 구하기
            if(GCD(newNumer, denom2) == 1)
            {
                answer[0] = newNumer;
                answer[1] = denom2;
            }
            else{
                answer[0] = newNumer/GCD(newNumer, denom2);
                answer[1] = denom2/GCD(newNumer, denom2);
            }
            
        }
        else
        {
            int lcm = LCM(denom1, denom2);
            int a = numer1 * (lcm/denom1);
            int b = numer2 * (lcm/denom2);
            int c = lcm;
            
            int nA = a + b;
            int nB = c;
            
            if(GCD(nA, nB) == 1)
            {
                answer[0] = nA;
                answer[1] = nB;
            }
            else
            {
                answer[0] = nA/(GCD(nA, nB));
                answer[1] = nB/(GCD(nA, nB));
            }           
                          
        }        
                        
        return answer;
    }

 

 

전체 코드

using System;

public class Solution 
{
    //numer 분자
    //denom 분모
    
    public int GCD(int a, int b)
    {
        while (b != 0)
        {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    
    public int LCM(int a, int b)
    {
        int result = (a * b) / GCD(a, b);
        return result;
    }
    
    public int[] solution(int numer1, int denom1, int numer2, int denom2) 
    {
        int[] answer = new int[2];
        
        if(denom1%denom2 == 0)
        {
            int a = numer1;
            int b = denom1;
            int c = numer2 * (denom1/denom2);
            
            int newNumer = a + c;
            
            //두 수의 최대공약수 구하기
            if(GCD(newNumer, denom1) == 1)
            {
                answer[0] = newNumer;
                answer[1] = denom1;
            }
            else{
                answer[0] = newNumer/GCD(newNumer, denom1);
                answer[1] = denom1/GCD(newNumer, denom1);
            }
            
        }
        else if(denom2%denom1 == 0)
        {
            int a = numer1 * (denom2/denom1);
            int b = denom2;
            int c = numer2;
            
            int newNumer = a + c;
            
            //두 수의 최대공약수 구하기
            if(GCD(newNumer, denom2) == 1)
            {
                answer[0] = newNumer;
                answer[1] = denom2;
            }
            else{
                answer[0] = newNumer/GCD(newNumer, denom2);
                answer[1] = denom2/GCD(newNumer, denom2);
            }
            
        }
        else
        {
            int lcm = LCM(denom1, denom2);
            int a = numer1 * (lcm/denom1);
            int b = numer2 * (lcm/denom2);
            int c = lcm;
            
            int nA = a + b;
            int nB = c;
            
            if(GCD(nA, nB) == 1)
            {
                answer[0] = nA;
                answer[1] = nB;
            }
            else
            {
                answer[0] = nA/(GCD(nA, nB));
                answer[1] = nB/(GCD(nA, nB));
            }           
                          
        }        
                        
        return answer;
    }
}