코딩테스트 예제
프로그래머스 분수의 덧셈
jineric
2023. 3. 21. 11:34
일단 문제를 풀기 위해서 알고리즘방식 중 하나인 유클리드 호제법을 알아야 한다.
유클리드 호제법
2개의 자연수의 최대공약수를 구하는 알고리즘의 하나
호제법은 두 수가 서로 상대방수를 나누어서 결국 원하는 수를 얻는 알고리즘
1 | 3 |
2 | 4 |
10
8
최대공약수의 분수형태로 만들어 놓기
기약분수로 만들기
조건식for문 돌려서 나눌수 있는 수를 나눌수 있게 하기
For(int I = N-1; I > 1; i--) {
If(N % I == 0 && denominator % I == 0){ | //N=10 % 9,8,7,6,5,4,3,2 | //D=8 % 9,8,7,6,5,4,3,2 |
두조건이 모두 나눠서 나머지값이 0이 나오면
N/=I; | N 나누기I |
D/=I; | D 나누기I |
class Solution {
public int[] solution(int numer1, int denom1, int numer2, int denom2) {
int N = (numer1 * denom2)+( denom1 * numer2 );
int D = ( denom1 * denom2);
for(int i = N-1; i>1; i--){
if(N % i == 0 && D % i==0){
N/=i;
D/=i;
}
}
int[] answer = {N,D};
return answer;
}
}