코딩테스트입문 / 분수의 덧셈(최대공약수:gcd)

📚문제

출처 : 코딩테스트입문 / 분수의 덧셈(https://school.programmers.co.kr/learn/courses/30/lessons/120808)

 

📝풀이

1. 단순 gcd(최대공약수) 활용한 Solution

def solution(numer1, denom1, numer2, denom2):

	#1. 두 분수의 합 계산
    boonja = (numer1 * denom2) + (numer2 * denom1)
    boonmo = (denom1 * denom2)
    
    #2. 최대공약수 계산
    start_num = max(boonja,boonmo) # 두 수 중에서 더 큰 숫자를 시작num으로 지정
    gcd_value = 0
    
    for num in range(start_num, 0, -1):
        if boonja % num ==0 and boonmo % ==0: # 분자와 분모 모두의 약수가되는 최대 숫자를 gcd_value로 지정
            gcd_value = num
            break # 최대 공약수를 찾기 위해 찾으면 break 해주기
    
    # gcd로 나눈 값을 answer에 담기
    answer = [boonja/gcd_value, boonmo/gcd_value]
    return answer

 

2. 최적화 된 gcd 활용 solution

# gcd 재귀함수 설정
def gcd(a, b):
    if a % b == 0:
        return b
    return gcd(b, a % b)

def solution(denum1, num1, denum2, num2):

    # 1. 두 분수의 합 계산
    boonmo = num1 * num2
    boonja = denum1 * num2 + denum2 * num1
    
    # 2. 최대공약수 계산
    gcd_value = gcd(boonmo, boonja)

    # 3. gcd 로 나눈 값을 answer에 담기
    answer = [boonja / gcd_value, boonmo / gcd_value]
    return answer

 

gcd 구하는 함수인데 , 바로 머릿속에서 저런 코드가 떠오르지는 않지만

예시를 들어서 넣어보면 쉽게 이해가 된다.

 

그리고 이런 코드는 가급적이면 외워놓는것이 좋다. 왜냐하면

1) 저 코드가 훨씬 효율적으로 동작하고 

2) 추후 문제풀이에도 유용하게 사용 가능

하기 때문

 

3. math 모듈 활용한 solution

import math # math 모듈 import

def solution(denum1, num1, denum2, num2):

    # 1. 두 분수의 합 계산
    boonmo = num1 * num2
    boonja = denum1 * num2 + denum2 * num1
    
    # 2. 최대공약수 계산
    gcd_value = math.gcd(boonmo, boonja)
    
    # 3. gcd 로 나눈 값을 answer에 담기
    answer = [boonja / gcd_value, boonmo / gcd_value]
    return answer

당연히 이게 math만 언급해주면 되기 때문에 제일 간단하다.

 

 

입문인데도 생각보다 쉽지 않아서 조금 당황...

그래도 최대공약수를 구하는 매커니즘에 대해서 한 번더 이해할 수 있는 계기가 되었다.

앞으로도 최대공약수 문제는 꾸준히 나온다고 하니 지금 잘 이해해놓고 응용해나가면 될 것 같다

 

 

 

 

 

 

+ 풀이 참고한 유튜브 링크 

분수의 덧셈(Lv0) - 파이썬 python 프로그래머스 문제 풀이 - YouTube