문제
첫 번째 분수의 분자와 분모를 뜻하는 numer1, denom1, 두 번째 분수의 분자와 분모를 뜻하는 numer2, denom2가 매개변수로 주어집니다. 두 분수를 더한 값을 기약 분수로 나타냈을 때 분자와 분모를 순서대로 담은 배열을 return 하도록 solution 함수를 완성해보세요.
- 제한사항
- 0 <numer1, denom1, numer2, denom2 < 1,000
풀이
이 문제에서 중요한 개념은 최대공약수와 최소공배수이다.
최대공약수와 최소공배수
- 최대공약수 : 두 정수의 공통 약수인 공약수 중 가장 큰 것
- 최소공배수 : 두 정수의 공통 배수인 공배수 중 가장 작은 것
ex) 180과 72의 최대공약수와 최소공백수 구하기
180 = 2^2 × 3^2 × 5
72 = 2^3 × 3^2
최대공약수 = 2^2 × 3^2 = 36
최소공배수 2^3 × 3^2 × 5 = 360
두 값을 구하는 과정에서 참고해야 할 알고리즘으로 유클리드 호제법이다.
유클리드 호제법에 따른 구현 공식은 다음과 같다.
최대공약수 구하기
→ b가 0이 될 때까지 a를 b로 나눈 나머지를 b에 다시 대입하는 과정을 반복
public static int gcd(int a, int b){ while(b != 0){ int temp = b; b = a % b; a = temp; } return a; }
최소공배수 구하기
→ 최소공배수의 성질 중 하나인 '두 수 a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수를 나눈 것과 같음'을 이용
public static int lcm(int a, int b){ return a * b / gcd(a, b); }
여러 시행 착오를 거치다 기약 분수를 구하기 위해 최대공약수와 최소공배수를 구해야겠다는 판단을 하고 난 뒤, 위 내용을 세세히 공부하느라 한참이 걸렸다^_ㅜ
두 값을 여러 번 사용할 거라 함수 형태로 만든 다음, 필요할 때마다 solution 함수 내에서 호출해 사용하기로 했다.
우선 최소공배수를 계산했다. 이후 두 분수의 분모를 최소공배수로 통일하여 분자를 계산한다. ex. numer1 * (lcm / denom1)
각 분모에 따라 최소공배수가 되기에 얼마 정도의 값이 필요한지 달라지므로 lcm/denom1 값을 기존 분자에 곱하면 된다.
다음으로 구한 분자를 더하고, 기약 분수로 변환해 주기 위해 분자와 분모의 최대공약수를 구한다. 분자와 분모를 각각 최대공약수로 나누어 주면 기약 분수를 구할 수 있기 때문이다.
ex. int gcd = gcd(sumNumer, lcm);
이때, 분모는 최소공배수가 된다. ex. denom1 = 2 denom2 = 4 → lcm = 4
분모가 다른 분수를 더할 때 하나의 분수로 통일하는 과정을 생각해 보면 쉽다.
그렇게 구한 분자와 분모를 기약 분수가 되도록 최대공약수로 나누면 끝이다.
처음에는 분모가 다른 경우, 분모 간 최대공약수를 갖는 경우, 분모 간 최대공약수를 갖지 않는 경우를 나누어 계산해 테스트 케이스를 통과했었는데 제출하고 처참한 실패의 향연.. 하하!
이번에 유클리드 호제법을 처음 맛 보았으니 다음에는 조금 더 쉬우려니 생각해 본다.
class Solution {
//최대 공약수를 구하는 함수
public int gcd(int a, int b) {
while (b != 0) {
int temp = a % b;
a = b;
b = temp;
}
return a;
}
//최소 공배수를 구하는 함수
public int lcm(int a, int b) {
return a * b / gcd(a, b);
}
public int[] solution(int numer1, int denom1, int numer2, int denom2) {
int[] answer = new int[2];
//최소 공배수(LCM) 계산
int lcm = lcm(denom1, denom2);
int newNumer1 = numer1 * (lcm / denom1);
int newNumer2 = numer2 * (lcm / denom2);
int sumNumer = newNumer1 + newNumer2;
int gcd = gcd(sumNumer, lcm);
//기약 분수로 변환
answer[0] = sumNumer / gcd;
answer[1] = lcm / gcd;
return answer;
}
}
결과
