알고리즘 #0004

• 문제 링크: 바로가기 (클릭)

I. 문제 상황

1. 초기 코드 작성

• 주어진 문제에 따라 최대공약수와 최소공배수를 구해야 한다.
• 먼저 아래의 [코드 1]처럼 최대공약수를 계산하는 메서드를 작성한다.
  • getGCD()를 재귀적으로 호출하면서 두 번째 인자에는 % 연산자를 통해 항상 첫 번째 인자보다 작은 값이나 0이 들어간다.
• [코드 1] 처음 작성한 코드 답안

    public int getGCD(int num1, int num2) {
        if (num1 % num2 == 0) {
            return num2;
        }
        return getGCD(num2, num1 % num2);
    }

---

• 입력한 배열에 원소가 한 개만 있을 경우 반복문을 실행하지 않고 바로 해당 원소를 반환한다.
• [코드 2]

class Solution {
    public int solution(int[] arr) {
        if (arr.length == 1) {
            return arr[0];
        }
        // ...
    }
}

---

• 입력한 배열에 원소가 두 개 이상이 있을 경우 반복문을 실행하여 최대공약수와 최소공배수 값을 계속 갱신한다.
• [코드 3] 전체 코드

class Solution {
    public int solution(int[] arr) {
        if (arr.length == 1) {
            return arr[0];
        }            
        int gcd = getGCD(arr[0], arr[1]);
        int lcm = (arr[0] * arr[1]) / gcd;
        for (int i = 2; i < arr.length; i++) {
            gcd = getGCD(lcm, arr[i]);
            lcm = (lcm * arr[i]) / gcd;
        }
        return lcm;
    }
    public int getGCD(int num1, int num2) {
        if (num1 % num2 == 0) {
            return num2;
        }
        return getGCD(num2, num1 % num2);
    }
}

2. 실행 결과

• 아래의 [결과 1]에서처럼 정상적으로 실행된다.
• [결과 1]