코딩테스트 입문 > 분수의 덧셈

# 분수의 덧셈

 

문제 설명
첫 번째 분수의 분자와 분모를 뜻하는 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 합니다.

 
 

처음 작성했던 답안

 

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int[] answer = new int[2];
        int numer3 = numer1*denom2 + numer2*denom1;
        int denom3 = denom1*denom2;
 
        
        answer[0] = numer3;
        answer[1] = denom3;
        
        return answer;
    }
}

 

 

위와 같이 작성할 경우

최대 공약수가 없을 경우 정답으로 인정될수있다.

하지만 문제에서 기약분수라고 했기 때문에 분모와 분자의 공약수가 1로 더 이상 나누어지면 안된다.

그렇기 때문에 위의 코드에 최대 공약수를 구하는 코드를 추가적으로 작성해주어야한다.

 

 

 

 

class Solution {
    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int[] answer = new int[2];
        int numer3 = numer1*denom2 + numer2*denom1;
        int denom3 = denom1*denom2;
        int max=0;
        for(int i=1; i<=numer3 && i<=denom3; i++){
            if(numer3%i==0 && denom3%i==0){
                max=i;
            }
        }
        
        answer[0] = numer3/max;
        answer[1] = denom3/max;
        
        return answer;
    }
}

 

 

 

 

 

이 문제는 유클리드 호제법을 이용하여 최대 공약수를 구해 효율적인 코드를 작성하도록 유도되는 문제이다.

 

유클리드 호제법(Euclidean algorithm)은 두 수의 최대 공약수(GCD)를 효율적으로 구하는 방법이다.

이 방법을 사용하면 반복적인 나눗셈을 통해 빠르게 GCD를 계산할 수 있다.

 

이 방법을 사용해 답변을 아래 코드와 같이 수정해보았다.

 

class Solution {
    // 유클리드 호제법을 이용하여 최대 공약수를 구하는 함수
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int[] answer = new int[2];
        // 두 분수의 합을 계산
        int numer3 = numer1 * denom2 + numer2 * denom1; // 새로운 분자
        int denom3 = denom1 * denom2; // 새로운 분모
        
        // 최대 공약수를 구해서 분자와 분모를 기약분수로 변환
        int gcd = gcd(numer3, denom3);
        answer[0] = numer3 / gcd;
        answer[1] = denom3 / gcd;
        
        return answer;
    }
}

 

1. gcd 메서드: 유클리드 호제법을 사용하여 두 수의 최대 공약수를 계산한다.
2. solution 메서드:
   • 두 분수의 합을 계산하여 새로운 분자(numer3)와 분모(denom3)를 구한다.
   • gcd 메서드를 사용하여 numer3과 denom3의 최대 공약수를 구한다.
   • 분자와 분모를 최대 공약수로 나누어 기약분수로 변환한다.