프로그래머스 - 최대공약수와 최소공배수 [자바]

• 문제 링크 : 최대공약수와 최소공배수

코딩테스트 연습 - 최대공약수와 최소공배수

 

정답(Solution)

import java.util.*;
class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];

        answer[0] = maxSame(n, m);
        answer[1] = minSame(n, m);

        return answer;
    }

    private int maxSame(int first, int second){
        int result = 0;

        List<Integer> iList1 = new ArrayList<>();
        for(int i=1; i<=first; i++){
            if(first % i == 0){
                iList1.add(i);
            }
        }


        List<Integer> iList2 = new ArrayList<>();
        for(int i=1; i<=second; i++){
            if(second % i == 0){
                iList2.add(i);
            }
        }

        for(int num1 : iList1){
            for(int num2 : iList2){
                if(num1 == num2 && result < num1){
                    result = num1;
                }
            }
        }

        return result;
    }

    private int minSame(int first, int second){

        int result = 0;

        int min = 0;
        int max = 0;

        if(first > second){
            max = first;
            min = second;
        }else{
            max = second;
            min = first;
        }

        int minSum = min;
        int maxSum = max;

        while(result == 0){

            if(min == max){
                result = min;
                return result;
            }

            min += minSum;

            if(min > max){
                max += maxSum;
            }
        }

        return result;
    }
}

 

분석

• 최대공약수는 각각의 약수들을 구한 후 공통 약수 중 가장 큰 것을 구하면 된다.
• 최소공배수는 작은 수를 증가시키면서 큰 수와 같아지는 경우 최소공배수이다.

---

• 최대공약수를 구하는 유클리드 호제법이 있다.
  위 알고리즘을 사용하면 간단히 최대공약수를 구할 수 있고
  최소공배수는 두 값의 곱을 나누면 나오기 때문에 최대공약수로 두 수의 곱을 나눠주면 된다.
• 수학을 알면 매우 쉽게 풀 수 있는 문제

 

분석 반영(유클리드 호제법)

class Solution {
    public int[] solution(int n, int m) {
        return new int[]{euclidean(n, m), n*m/euclidean(n,m)};
    }

    private int euclidean(int a, int b){
        if(b == 0){
            return a;
        }else{
            return euclidean(b, a % b);
        }
    }
}