[프로그래머스/JAVA] 최대공약수와 최소공배수

https://school.programmers.co.kr/learn/courses/30/lessons/12940?language=java

프로그래머스

📌 문제 요약 

두 수의 최대공약수와 최소공배수를 반환하는 함수 solution을 작성하는 문제였습니다.
입력으로 두 자연수 nnn, mmm이 주어지고, 출력으로 최대공약수와 최소공배수를 배열로 반환해야 합니다.
예:

• solution(3, 12) → [3, 12]
• solution(2, 5) → [1, 10]

 

---

[ 오답 노트 ]
❌ 기존 오답 코드

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        //  3   3 12    //  1   2   5
        //      1  4    //      2   5
        
        // 최소 공약수 
        // 1~12수 중에서 3이나 12로 나눠지는 수중에서 제일 작은 수?
        // 없으면 1반환?
        if(n < m) {
            for(int i = n; i < m; i++) {
                if(m % i == 0) {
                    answer[0] = i;
                    answer[1] = (m / i) * i;
                    break;
                }else{
                    answer[0] = 1;
                    answer[1] = n * m;
                    break;
                }
            }
        }else {
            for(int i = m; i < n; i++) {
                if(n % i == 0) {
                    answer[0] = i;
                    answer[1] = (n / i) * i;
                    break;
                }else{
                    answer[0] = 1;
                    answer[1] = n * m;
                    break;
                }
            }
        }
        return answer;
    }
}

📌 기존 코드의 문제점

 

1. 최대공약수 계산 로직의 오류

 

• if (m % i == 0) 또는 if (n % i == 0)의 조건이 잘못되었습니다.
• 반복문 for에서 iii를 증가시키면서 나눗셈으로 최대공약수를 찾는 방식은 비효율적일 뿐만 아니라, 정확하지도 않습니다.
• 최대공약수는 두 수의 공약수 중 가장 큰 값을 찾아야 하지만, 이 코드는 작은 값부터 순차적으로 찾다가 첫 번째 조건에서 break를 걸어 종료합니다.

 

 

2. 최소공배수 계산 방식의 오류

 

• (m / i) * i 또는 (n / i) * i는 단순히 m 또는 n 자체를 반환할 뿐입니다.
• 최소공배수는 정확히 (n∗m)/최대공약수(n * m) / 최대공약수(n∗m)/최대공약수 로 계산해야 합니다.

 

 

3. 중복된 반복문 구조

 

• n<m인지 여부에 따라 코드를 두 번 작성하여, 비효율적이고 가독성이 떨어집니다.
• 조건 분기 없이 한 번의 계산으로 처리할 수 있습니다.

 

 

4. 불필요한 else 구문과 break

else에서 최대공약수를 찾지 못하면 기본적으로 1이 반환되는데, 반복문 내에서 break를 남발하여 로직이 흐트러집니다.

 

 

 

---

[ 정답 코드 & 올바른 풀이 ]

 

📌 올바른 풀이

1. 최대공약수 (GCD) 계산 - 유클리드 호제법

 

• 유클리드 호제법은 두 수의 최대공약수를 효율적으로 계산하는 방법입니다.
• 원리: 두 수 a,b의 최대공약수는 b와 a%b의 최대공약수와 동일합니다.  (b = 0일 때, a가 최대공약수가 된다)

 

 

2. 최소공배수 (LCM) 계산

최소공배수는 두 수의 곱을 최대공약수로 나누면 계산됩니다.

LCM=(n∗m)/GCD

 

 

3. 코드 구조 간소화

 

• if-else와 중복된 반복문을 제거하여 코드 가독성과 효율성을 개선했습니다.
• 모든 입력에 대해 동일한 로직을 실행하도록 작성했습니다.

 

 

---

📌 정답 코드

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];

        // 최대공약수 계산 (유클리드 호제법)
        int gcd = gcd(n, m);

        // 최소공배수 계산
        int lcm = (n * m) / gcd;

        answer[0] = gcd; // 최대공약수
        answer[1] = lcm; // 최소공배수

        return answer;
    }

    // 유클리드 호제법을 사용한 최대공약수 계산 함수
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}