원하는 개수의 정수들의 최대공약수 출력 (JAVA)

최대공약수 구하기 응용

- 원하는 개수의 정수들의 최대공약수 -

저번 포스팅에서 2개의 수의 최대공약수를 구하는 프로그램을 만들어 본 적이 있었다.

그로부터 꽤 시간이 지난 지금 최대공약수를 더 쉽게 구할 수 있는 알고리즘을 배웠다.

그림으로 그 예제를 설명하겠다.

위 24, 15, 48 세 수의 최대공약수를 구한다고 가정했을 때

먼저 세 수중 최솟값을 구해준다. (예제에서는 15)

최솟값을 구하는 방법은 먼저 배열에 사용자에게 입력받은 정수를 넣어준 다음

정렬을 하여 낮은값부터 높은값까지 오름차순으로 정렬해주면 배열의 가장 앞의 값 arr[0]의 값이 최솟값이 된다.

그 다음 최대공약수의 특징을 생각하면 문제는 쉽게 풀린다.

최대공약수는 각 정수들이 모두 나누어 떨어지는 값 중 가장 큰 수를 말한다.

따라서 최솟값으로 각 정수들을 나눈 나머지값을 비교해서 그 수가 모두 0이 나오면 최솟값이 최대공약수가 된다.

만약 최솟값으로 나눈 나머지값이 모두 0이 아니였다면 최솟값을 1씩 감소시키면서

다시한번 정수들의 나머지값을 비교해보며 나머지가 모두 0이 나올때까지 반복하면 된다.

그럼 코드를 공개하겠다.

(코딩은 간만에 자바로 짜봤다. 요즘 자바를 공부하는 중이라..)

import java.util.Scanner;
 
public class GetGCD {
 
    static void sort(int arr[], int number) {
        int least, tmp, i ;
        for (i = 0; i < number - 1; i++) {
            least = arr[i];
            for (int j = i + 1; j < number ; j++) 
                if (least > arr[j]) {
                    tmp = arr[j];
                    arr[j] = least;
                    least = tmp;
                }
            arr[i] = least;
        }
    }
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        System.out.print("최대공약수를 구할 숫자들의 개수를 입력하세요: ");
        int number = sc.nextInt();
        
        int[] arr = new int[number];
        System.out.print("정수들을 입력하세요: ");
        for (int i    =    0;     i    <    number;    i++) {
            arr[i] = sc.nextInt();
        }
        // 낮은 수부터 높은 수까지 차례대로 정렬
        sort(arr, number);
        
        //최대공약수는 정수들 중 최소값부터 1씩 감소시킨 값으로
        //정수들을 나눠 모두 나누어 떨어지는 값 중 가장 큰 값이다.
        int min = arr[0], result;
        for(int i = 1; i < number; i++) {
            if ( (arr[i] % min) == 0 )
                continue;
            else {
                // 나누어 떨어지지 않으면 최소값 - 1 감소시키고
                // i = 0 으로 만듦으로써 반복을 처음부터 다시 실행시킨다.
                min--;
                i = 0;
                continue;
            }
        }
        result = min;
        System.out.println("입력한 수들의 최대공약수는 : "+result+" 입니다.");
    }
 
}

프로그램을 짜면서 가장 고민한 부분은 나머지값 비교하는 반복문 구성이였다.

배열 안의 값들을 방문하여 하나하나 나머지값을 비교해봐야 했기 때문에 반복문을 이용하긴 해야겠는데

모든 나머지값이 0일 때 나눈 값을 구해야해서 조금 까다롭긴 했지만

continue를 이용해 만약 나머지값이 하나라도 0이 아니면 (else 문 { } 부분)

최솟값 min을 1 감소시키고 반복문 변수 i = 0으로 다시 만든다음 continue를 해

반복을 처음부터 다시 실행시키도록 구성하였다.

<결과창/>