프로그래머스 최대공약수와 최소공배수 JAVA 풀이 (유클리드호제법, 시간복잡도)

유클리드 호제법을 활용하여 최대공약수(GCD)와 최소공배수(LCM)를 구하는 문제입니다.

---

Q

두 수 n, m이 주어질 때:

• 최대공약수
• 최소공배수

를 배열 형태로 반환하는 문제

---

정답

package level1;

public class No33 {
    class Solution {
        public int[] solution(int n, int m) {

            int gcd = getGCD(n, m);

            return new int[]{
                    gcd,
                    (n * m) / gcd
            };
        }

        public static int getGCD(int n, int m){
            if(n % m == 0){
                return m;
            }

            return getGCD(m, n % m);
        }
    }
}

---

📌 나의 오류

처음에는 ArrayList\[\] 타입으로 반환하려고 했다.

ArrayList<Integer>[] solution(...)

하지만 실제로는 ArrayList 객체 하나만 생성해서 타입 오류가 발생했다.

또한 문제는 배열 반환을 요구하므로 int\[\] 형태로 반환해야 한다.

---

📌 핵심 포인트

유클리드 호제법

두 수의 최대공약수를 빠르게 구하는 대표 알고리즘이다.

GCD(a,b)=GCD(b,a bmod b)

동작 예시

12, 18
→ 18 % 12 = 6
→ 12 % 6 = 0
→ 최대공약수 = 6

---

📌 최소공배수 공식

LCM = (n * m) / GCD

최대공약수를 이용하면 최소공배수도 쉽게 구할 수 있다.

---

📌 한 줄 정리

• 최대공약수는 유클리드 호제법 사용
• 최소공배수는 (n \* m) / gcd
• 반환 타입은 int\[\]

---

📌 최종 핵심 요약

• 유클리드 호제법은 코딩테스트 단골 알고리즘
• 재귀 흐름 이해가 중요
• GCD와 LCM은 자주 함께 출제된다.

---

꾸준히 기본 수학 알고리즘을 익혀두면 이후 구현 문제에서도 큰 도움이 된다