[프로그래머스 입문 / 파이썬] 분수 덧셈

실습코드 :

https://colab.research.google.com/drive/13rSz5LZ8KtI0pj7NYghyjsKJxqR3HB8K?usp=sharing

Untitled12.ipynb

Colab notebook

colab.research.google.com

문제 설명

첫 번째 분수의 분자와 분모를 뜻하는 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:
$$\frac{1}{2} + \frac{3}{4} = \frac{5}{4}$$
- 입니다. 따라서 [5, 4]를 return 합니다.
입력 예 #2: ( \frac{9}{2} + \frac{1}{3} = \frac{29}{6} )입니다. 따라서 [29, 6]을 return 합니다.

문제 풀이 설명

두 분수를 더한 후 기약 분수로 나타내기 위해 다음의 단계를 따릅니다:

두 분수를 공통 분모로 맞춥니다.
분자끼리 더한 값을 계산합니다.
기약 분수로 나타내기 위해 최대공약수(GCD)를 구해 분자와 분모를 나눕니다.

코드 구현

import math

def solution(numer1, denom1, numer2, denom2):
    # 공통 분모를 구함
    common_denom = denom1 * denom2
    # 분자 계산
    common_numer = numer1 * denom2 + numer2 * denom1
    # 최대공약수를 구해 기약 분수로 만듦
    gcd = math.gcd(common_numer, common_denom)
    return [common_numer // gcd, common_denom // gcd]

# 테스트 예시
print(solution(1, 2, 3, 4))  # 결과: [5, 4]
print(solution(9, 2, 1, 3))  # 결과: [29, 6]

풀이법 2: 분수 모듈 사용

파이썬의 fractions 모듈을 사용하면 더 간단하게 분수 덧셈을 처리할 수 있습니다.

from fractions import Fraction

def solution(numer1, denom1, numer2, denom2):
    # 분수 객체를 생성하여 더한 뒤 기약 분수로 변환
    result = Fraction(numer1, denom1) + Fraction(numer2, denom2)
    return [result.numerator, result.denominator]

# 테스트 예시
print(solution(1, 2, 3, 4))  # 결과: [5, 4]
print(solution(9, 2, 1, 3))  # 결과: [29, 6]

풀이법 3: 유클리드 호제법을 통한 최대공약수 계산

기약 분수를 구하기 위해 유클리드 호제법을 사용하여 최대공약수를 계산할 수 있습니다.

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def solution(numer1, denom1, numer2, denom2):
    # 공통 분모를 구함
    common_denom = denom1 * denom2
    # 분자 계산
    common_numer = numer1 * denom2 + numer2 * denom1
    # 최대공약수를 구해 기약 분수로 만듦
    gcd_value = gcd(common_numer, common_denom)
    return [common_numer // gcd_value, common_denom // gcd_value]

# 테스트 예시
print(solution(1, 2, 3, 4))  # 결과: [5, 4]
print(solution(9, 2, 1, 3))  # 결과: [29, 6]

계산 복잡도

첫 번째 방법: O(log(min(a, b))) - 최대공약수를 구하는데 걸리는 시간 복잡도.
두 번째 방법: O(log(min(a, b))) - fractions 모듈 내부적으로 최대공약수를 구하는데 걸리는 시간 복잡도.
세 번째 방법: O(log(min(a, b))) - 유클리드 호제법을 사용하여 최대공약수를 구하는데 걸리는 시간 복잡도.