[문제 풀이][Java] 백준 1037번 약수

[문제 풀이][Java]  백준 1037번 약수

* 학습 목적의 게시물이나 혹시 이 게시물이 문제가 된다면 언제든 연락 부탁드립니다.

* 더 나은 풀이를 위한 훈수, 조언 등 모두 환영합니다!

문 제 

양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다.

어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.

입 력

첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다.

둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고,

2보다 크거나 같은 자연수이고, 중복되지 않는다.

출 력

첫째 줄에 N을 출력한다. N은 항상 32비트 부호있는 정수로 표현할 수 있다.

[문제 링크] 백준 1037번 약수

---

문제 해석

• 주어지는 수들은는 1과 원래 수 N을 제외한 모든 약수이다.
• N은 1,000,000보다 작거나 같기에 int로 받을 수 있다.

해결 방법

• N과 1을 포함한 약수를 내림차순한 배열에서 약수는 숫자쌍을 이룬다.
  • 예를 들어, 16의 약수 배열은 [1, 2, 4, 8, 16] 이다.
  • 1 × 16, 2 × 8, 4 × 4는 모두 원래의 수인 16이다.
• 위 원리를 이용하여 간단하게 주어진 1과 N을 제외한 N의 약수를 내림차순한 배열에서 첫 번째 수와 마지막 수를 곱하면 원래 수를 알 수 있다.

참고사항

• [알고리즘][java] 주어진 수 N의 약수 구하기 구현

전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		// 입력 받기
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int numberOfDivisors = Integer.parseInt(br.readLine());
		
		int[] divisors = new int[numberOfDivisors];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < divisors.length; i++) {
			divisors[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(divisors);
		
		int answer = divisors[0] * divisors[divisors.length - 1];
		
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		bw.write(String.valueOf(answer));
		bw.flush();
		
		br.close();
		bw.close();
	}
}