연습문제 1-2(3) N개의 최대공약수 구하기

문제 설명

정수 배열 A에는 0보다 큰 숫자가 N개 들어있습니다.

N개의 모든 숫자를 아우르는 최대 공약수를 구하는 프로그램을 구현하세요.

---

입력 형식

• A: 자연수가 담긴 정수 배열

---

출력 형식

• 최대 공약수를 정수로 반환

---

제약 사항

• 0 < A.length <= 1000
• 0 < A[i] <= 100

---

입출력 예시

• 입력
  • A = {6, 12, 4}
• 출력: 2
• 설명: 모든 세 숫자의 최대 공약수는 2이다.

---

작성 코드

(16/20)

public class test123 {
    static int sort(int[] A, int number) {
        int gcd = A[0];
        for (int i = 1; i < number; i++) {
            gcd = gcd(gcd, A[i]);
        }
        return gcd;
    }

    static int gcd(int a, int b) {
        if (a == 0) {
            return b;
        } else {
            return gcd(b % a, a);
        }
    }

    public static void main(String[] args) {
        int[] arr = {6, 12, 4};
        int gcd = test123.sort(arr, arr.length);
        System.out.println("최대 공약수: " + gcd);
    }
}

 

메소드는 먼저 배열 A의 첫 번째 요소를 gcd에 저장한다. 

그리고 배열 A의 나머지 요소들과 gcd를 차례대로 최대공약수를 구해 gcd에 덮어쓰기를 한다.

최종적으로 gcd에는배열 A의 모든 요소들의 최대공약수가 저장된다.

 

이 메소드에서 사용된 gcd 함수는 유클리드 호제법을 사용하여 최대공약수를 계산한다.

a와 b를 입력으로 받아, a가 0이 될 때까지 b % a를 b에 대입하고 a를 b에 대입하는 과정을 반복한다.

그리고 a가 0이 되면, b를 반환한다.

main 함수는 이 sort 메소드를 호출하고, 배열 {6, 12, 4}와 배열의 길이인 3을 인자로 전달한다.

 

이 메소드에서 사용된 gcd 함수는 유클리드 호제법을 사용하여 최대 공약수를 계산합니다. a와 b를 입력으로 받아, a가 0이 될 때까지 b % a를 b에 대입하고 a를 b에 대입하는 과정을 반복합니다. 그리고 a가 0이 되면, b를 반환합니다.

main 함수는 이 sort 메소드를 호출하고, 배열 {6, 12, 4}와 배열의 길이인 3을 인자로 전달합니다. 그리고 반환된 최대 공약수를 출력합니다.