코딩 테스트/9. ...

분수의 덧셈

길동이이이잉 2024. 4. 26. 19:53
728x90
반응형

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

 

import java.util.*;

class Solution {
    public int[] solution(int n1, int d1, int n2, int d2) {
        int den = d1 * d2;
        int num = n1 * d2 + n2 *d1;
        
        int gcd = gcd(num, den);
        
        num /= gcd;
        den /= gcd;
        
        return new int[]{num, den};
    }
    
    public int gcd(int a, int b){
        while(b != 0){
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
}

 

※유클리드 호제법 : 큰 수를 작운 수로 나누어서 나머지를 구하는 과정을 반복하면서 최대공약수를 찾는 방법

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

* 호제법 - 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘

import math

def solution(n1, d1, n2, d2):
    answer = []
    den = d1 * d2;
    num = n1 * d2 + n2 * d1;

    gcd = math.gcd(den, num)
    #최대 공약수 = gcd
    #최소 공배수 = lcm

    den = den / gcd
    num = num / gcd

    answer.append(num)
    answer.append(den)

    return answer
    
    
###################
 def 최대공약수(a, b):
 	while b != 0:
    	a, b = b, a % b
    return a
    
최소 공배수 = (a * b) // 최대공약수(a, b)

 

 

 

from fractions import Fraction

def solution(denum1, num1, denum2, num2):
    answer = Fraction(denum1, num1) + Fraction(denum2, num2)
    return [answer.numerator, answer.denominator]
728x90
반응형