[프로그래머스 Lv.1 - Java] 최대공약수와 최소공배수

문제 설명

https://programmers.co.kr/learn/courses/30/lessons/12940

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

---

문제 풀이

public class Sol44 {
    public int[] solution(int n, int m) {
        int[] answer = {n, m};
        int max = n, min = m;
        int remainder;
        if (n == m) {
            return answer;
        } else if (m > n) {
            max = m;
            min = n;
        }

        while (min != 0) { //나머지가 있으면
            remainder = max % min; // 큰수에서 작은 수를 나눈 나머지
            max = min; //나눠질 수를 설정
            min = remainder; //나눌 수를 설정
        }
        answer[0] = max; //최대공약수
        answer[1] = max * (n / max) * (m / max); //최대공약수로 나눈 몫끼리 곱 * 최대공약수 하면 최소공배수!!

        return answer;
    }

    public static void main(String[] args) {
        Sol44 method = new Sol44();
        for (int i : method.solution(3, 12)) {
            System.out.print(i + " ");
        }
    }
}

유클리드 호제법을 반복문으로 간단하게 구현해보았다! 최소공배수의경우 최대공약수를 알면 쉽게 구할 수 있다. 재귀함수를 사용해서 구현할 수도 있지만 실행 시간면에서 반복문으로 구현하는 것이 더 좋을 것이라고 생각하여 반복문으로 구현을 해보았다.

---

관련 개념

유클리드 호제법은 다음과 같다.

 

기존 최대공약수 계산법의 단점

1. 숫자가 크면 계산이 복잡하다
    : 위 계산식에서 보듯이 숫자가 커지면 커질수록 엄청 많이 나누어야 한다!
    : 코드로 구현하면 짝수인지 홀수인지 판단 후 나눠야 하므로 연산이 더욱 많다.

2. 약수 찾기가 어렵다
    : 위와 같은 개념으로 최대 공약수를 계산하는 것이 복잡하면 약수를 찾는 것 또한 복잡하다.