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

SUIN2 2024. 12. 16. 22:32

문제 설명

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

제한사항

0 <numer1, denom1, numer2, denom2 < 1,000

입출력 예

입출력 예 설명

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

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

오늘부터 코딩테스트 준비를 시작했다. 기업에서 프로그래머스 활용을 많이 한다고 해서, 기존에 연습했던 백준에서 벗어나 프로그래머스에서 새롭게 다시 시작한다. 오래만에 하기도 하고, 코딩테스트에 매우매우 자신이 없기 때문에 완전 기초부터 다시 한다는 마음으로 했다. 초반 사칙연산까지는 가볍게 패스했으나 .. 요번 '분수의 덧셈'부터 난관에 봉착했다. 고심해서 푼 문제, 혹은 외워두면 좋을 문제들은 티스토리에 업로드하려고 한다. 고럼 시작 !

일단 이 문제는 리스트 형태의 출력이고, 다른 사람들이 작성한 답변을 슬쩍 봤을땐 기존 solution 함수와 최대공약수를 구하는 GCD 함수 두 가지로 동작했다. 지피티에게 물어보니, math 메서드를 쓰지 않고, 알고리즘을 기반으로 최대공약수를 구할땐 유클리드 알고리즘을 사용한다고 한다. 유클리드 알고리즘이란, 두 수 a, b에 대해 a를 b로 나눈 나머지를 r이라고 하면, gcd(a, b) = gcd(b, r)으로 동작하고, 이때 r이 0이 되면 그때의 b값이 두 수의 최대공약수가 된다고 한다.

따라서, GCP의 함수는 다음과 같다.

def GCD(a, b): # 최대공약수: Greatest Common Divisor
    while b: # b가 0이 아니면 계속 반복
        a, b = b, a%b
    return a

유클리드 거리는 들어봤어도, 유클리드 알고리즘은 처음 접해보았다. 원리가 비슷한가 ? 잘 모르겠지만, 아무튼 동작 과정은 다음과 같다.

a = 12, b = 30 일때,

1. 12, 30 = 30, 6

2. 30, 6 = 6, 0

return 6 # 12와 30의 최대공약수는 6이다.

전체 코드는 다음과 같다. 최대공약수를 각 통분하여 더한 수에 나누어주면 된다.

def solution(numer1, denom1, numer2, denom2):
    numer = numer1*denom2 + numer2*denom1
    denom = denom1*denom2
    answer = GCD(numer, denom)
    return numer//answer, denom//answer

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

끝 !