[JAVA-자바] 1037번: 약수

 

양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다.
어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.

 

이 말은 즉 N이 만약 8이라고 가정했을 때, 약수(A)는 1,2,4,8입니다.
그러나 문제에서 정의내린 진짜 약수는 약수(A)는 1과 N(자기자신)이 아니여야만 합니다.

그렇기 때문에 예제1번의 경우에는 1,2,4,8 에서 1과 8을 제외한 2와 4가 진짜 약수입니다.

 

예제3번의 경우에는 N이 24라고 가정했을 때, 약수(A)는 1,2,3,4,6,8,12,24입니다.
진짜 약수는 1과 24를 제외한 2,3,4,6,8,12 가 진짜 약수가 되는 것 입니다.

예제1: 2 * 4 = 8

예제2: 2 * 2 = 4

예제3: 2 * 12 = 24

 

이쯤에서 알게 된 사실은 진짜 약수(A)에서 최솟값 * 최댓값 을 구하면 N이 됩니다.

그렇다면 약수를 입력받고, 오름차순or내림차순 정렬을 수행한 이후에

배열의 첫번째 요소 * 배열의 마지막 요소 = N이 나오겠습니다.

 

시간복잡도&최적화 관련은 연관된 다른 문제에서 다루도록 하겠습니다!

 

소스코드:

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int size = sc.nextInt();
    int[] arr = new int[size];

    for (int i = 0; i < size; i++) {
        arr[i] = sc.nextInt();
    }

    sc.close();

    Arrays.sort(arr);

    System.out.println(arr[0] * arr[size - 1]);
}

 

글의 내용 중 잘못된 점이나 수정이 필요한 부분, 혹은 궁금한 사항이 있다면 언제든 댓글로 남겨주시면 감사하겠습니다.

여러분의 피드백은 더 나은 글을 작성하는 데 큰 도움이 됩니다. 감사합니다.