문제 설명
첫 번째 분수의 분자와 분모를 뜻하는 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] |
class Solution {
static int gcd(int a, int b) {
if (a % b == 0) {
return b;
} return gcd(b, a % b);
}
public int[] solution(int numer1, int denom1, int numer2, int denom2) {
int[] answer = new int[2];
int sum1 = ((numer1 * denom2) + (numer2 * denom1));
int sum2 = (denom1 * denom2);
answer[0] = sum1 / gcd(sum1, sum2);
answer[1] = sum2 / gcd(sum1, sum2);
return answer;
}
}
이번 문제는 두 가지를 할 줄 알아야 합니다. 바로 분수끼리 계산하는 법과 최대 공약수를 구하는 법입니다. 수학책을 집어본 지도 가물가물해서 분수의 존재조차 잊어버리고 살았습니다. 그래도 이 부분은 쉬운 편입니다.
A / B + C / D = ((A * D) + (B * C)) / (B * D) |
위의 코드에서는 sum1과 sum2에 해당하는 부분입니다. 하지만 문제가 있다면, 위는 단순 계산식으로 문제에서 원하는 기약 분수가 아니라는 점입니다. 기약 분수의 사전적 정의는 '분모와 분자 사이의 공약수가 1뿐이어서 더 이상 약분되지 않는 분수'를 뜻합니다. 분자와 분모의 최대 공약수(Greatest Common Divisor, GCD)로 나누어주는 과정이 필요합니다. 최대 공약수의 사전적 정의는 '둘 이상의 정수의 공약수 가운데 가장 큰 수'입니다. 최대 공약수가 아닌 공약수로 약분한다면 약분된 분수일 뿐, 기약 분수라고 할 수는 없겠죠.
본론으로 돌아와, 저는 재귀함수를 사용했습니다. 이외에 '유클리드 호제법', '빅인티저(Biginteger)', '브루트 포스(Brute Force)' 방법 등이 있습니다. 제가 쓴 재귀함수도 엄밀히 말하면 유클리드 호제법에 속하는 방식인 듯한데 정확히는 저도 잘 모르겠습니다. 조금 더 공부가 필요할 듯 하네요.
유클리드 호제법은 최대 공약수를 구하는 알고리즘으로, 두 수 a, b의 GCD는 b와 a%b의 GCD와 같다는 것을 이용하는 원리입니다. 아래 코드는 유클리드 호제법과 반복문을 이용한 코드입니다.
public static int gcd(int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
아래 코드는 빅인티저 클래스를 이용한 방식입니다. 이 클래스는 gcd() 메소드를 제공하기 때문에 간편하게 구할 수 있습니다. 장점과 단점까지는 몰라서, 나중에 알게되면 추가하겠습니다.
import java.math.BigInteger;
public static BigInteger gcd(BigInteger a, BigInteger b) {
return a.gcd(b);
}
아래 코드는 브루트 포스 방식입니다. 두 수의 모든 약수를 구하고, 공통된 약수 중에서 가장 큰 값을 구하는 방법입니다. '모든' 수를 구하는 방법답게 시간 복잡도가 O(n)이므로, 큰 수에는 쓰지 않는 것이 효율적입니다.
public static int gcd(int a, int b) {
int gcd = 1;
for (int i = 1; i <= a && i <= b; i++) {
if (a % i == 0 && b % i == 0) {
gcd = i;
}
}
return gcd;
}
최대 공약수를 구하는 다양한 방법을 알아보았습니다. 유클리드 호제법 정도만 알아도 지장은 없겠지만, 다양한 방법으로 구현할 수 있다면 언젠가는 쓰일지도 모를 일이니까요.
문제를 풀면서 많이 슬펐네요. 2일차 문제 치고는 조금 악랄한 문제였던 것 같습니다….
'프로그래머스 > Lv. 0(코딩테스트 입문)' 카테고리의 다른 글
[프로그래머스 코딩테스트] 나머지 구하기(Java) (0) | 2023.03.22 |
---|---|
[프로그래머스 코딩테스트] 배열 두 배 만들기(Java) (0) | 2023.03.22 |
[프로그래머스 코딩테스트] 숫자 비교하기(Java) (0) | 2023.03.21 |
[프로그래머스 코딩테스트] 두 수의 나눗셈(Java) (0) | 2023.03.21 |
[프로그래머스 코딩테스트] Day 1. 사칙연산(Java) (0) | 2023.03.21 |