분수의 덧셈_programmers_lev00

<코딩 테스트>

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

 

<나의 풀이 과정>

*우선 기초 최대 공약수와 최소 공배수의 개념에 대해 정리했습니다.

최대공약수(GCD, Greateast Common Division)와 최소공배수(LCM, Least Common Multiple)입니다. 

먼저 두 수를 소인수분해를 한 뒤, 두 수의 공통된 소인수를 모두 곱하면 최대공약수, 두 수의 모든 소인수를 곱하면 최소공배수가 되죠.

예를 들어 들어오는 수가 (1,2,3,4) 이면 

이렇게 분수를 다 더해주고

최대 공약수를 찾은 다음에 

분모=8, 분자=10 을 각각 최대 공약수로 나눈 값을

answer[0,1]번째에 넣어주었습니다!!!

 

package com.programmers.level00.분수의덧셈;

public class Test {

	public static void main(String[] args) {
		System.out.println(solution(1, 2, 3, 4));
	}

	static int[] solution(int denum1, int num1, int denum2, int num2) {
		int[] answer = new int[2];

		//1. 우선 분모 분자를 먼저 곱해주고
		int dNum = denum1 * num2 + denum2 * num1;
		int num = num1 * num2;
		// 최대 공약수로 분수를 약분하는 것은 나중으로 뺌!

		//2. index에 공통으로 어디까지 나눌건지 정함-> 더큰수를 지정
		int index = num > dNum ? num : dNum;

		//3. 최대 공약수 구하기
		int gcd = 1;

		// 분자와 분모중에 더 큰수 10이 될때까지 나눠서 둘다 나눠지는 수 중 최대 수 찾기
		for (int i = 2; i <= index; i++) {
			gcd = num % i == 0 && dNum % i == 0 ? i : gcd;
		}

		//4. 분자와 분모를 최대 공약수로 나눠서 기약분수를 만들기!
		answer[0]=dNum/gcd;
		answer[1]=num/gcd;

		System.out.println("결과출력");
		for (int i : answer) {
			System.out.print(i);
		}
		return answer;
	}
}

 

 

<다른 사람 풀이>

class Solution {
    public int[] solution(int denum1, int num1, int denum2, int num2) {
        int[] result = new int[2];
        // 분모의 최소공배수를 구한다.
        result[0] = denum1*num2 + denum2*num1;
        result[1] = num1*num2;
        int min = (result[0] > result[1])? result[0]: result[1];
        int gcd = 0;
        for (int i = 1; i <= min; i++) {
            if (result[0] % i == 0 && result[1] % i == 0)
                gcd = i;
        }
        result[0] = result[0]/gcd;
        result[1] = result[1]/gcd;

        return result;
    }
}

<다른 사람 풀이>

class Solution {
    public int[] solution(int denum1, int num1, int denum2, int num2) {
        int denum = denum1 * num2 + denum2 * num1;
        int num = num1 * num2;

        int gcd = getGCD(denum, num);


        return new int[]{denum / gcd, num / gcd};
    }

    public int getGCD(int a, int b) {
        if (a % b == 0) {
            return b;
        }

        return getGCD(b, a%b);
    }
}

 

 

 

 

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/120913

프로그래머스