[알고리즘] 프로그래머스 : 최대공약수와 최소공배수

알고리즘 문제 출처 : 프로그래머스 https://programmers.co.kr/learn/courses/30/lessons/12940

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

 

---

내가 작성한 코드

예외가 터져서 throws로 던졌는데 계속 에러가 나서 try~catch문으로 잡았더니 잡혔다. n과 m 중 0이 주어졌을 때 0으로 나누게 되어 터지는 ArithmeticException이었다.

경우를 1) 한 수가 다른 수의 최대공약수인 경우 2) 한 수와 다른 수의 최대공약수가 따로 존재하는 경우 3) 두 수가 서로소인 경우, 이렇게 세 가지로 나누었다. 두번째 경우에서 최소공배수를 구할 때 그냥 n과 m을 서로 곱한 뒤 최대공약수 answer[0]이나 i로 나누어주면 되는데(최대공약수가 두번 곱해진 꼴이니까) 너무 복잡하게 생각했던 것 같아 아쉽다.

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        try {
            if(Math.max(n, m) % Math.min(n, m) == 0) {
                answer[0] = Math.min(n, m);
                answer[1] = Math.max(n, m);
            }
            else {
                for(int i = 2; i <= Math.min(n, m)/2; i++) {
                    if(Math.max(n, m) % i == 0 && Math.min(n, m) % i == 0) {
                        answer[0] = i;
                        answer[1] = i * (Math.max(n, m)/i) * (Math.min(n, m)/i);
                    }
                }

            }
            if(answer[0] == 0) {
                answer[0] = 1;
                answer[1] = Math.max(n, m) * Math.min(n, m);
            }
        }catch(ArithmeticException e) {

        }
        return answer;
    }
}

 

위 문제는 유클리드 호제법으로 풀면 더 쉽게 풀 수 있다. 대학교 때 수학의 이해라는 과목을 들은 적이 있는데 그 때 유클리드 기하학/비유클리드 기하학과 함께 유클리드 호제법을 만났던 기억이 어렴풋이 난다. 역시 수학은 계속해서 관심을 가지고 봐야 한다. 유클리드 호제법 기억해둬야지.

 

관련 : 

네이버 지식백과 유클리드 호제법 https://terms.naver.com/entry.nhn?docId=2073670&cid=47324&categoryId=47324

숫자 알고리즘 - 유클리드 호제법 https://blog.naver.com/z1004man/221809239699

유클리드 호제법 증명 https://www.youtube.com/watch?v=J5Yl2kHPAY4