import java.util.*;
class Solution {
public int solution(int[] arrayA, int[] arrayB) {
int answer = 0;
int chulGcd = gcd(arrayA);
int youngGcd = gcd(arrayB);
for(int num : getDivisors(chulGcd)) {
if(!canDivideAll(num, arrayB)) {
answer = Math.max(answer, num);
}
}
for(int num : getDivisors(youngGcd)) {
if(!canDivideAll(num, arrayA)) {
answer = Math.max(answer, num);
}
}
return answer;
}
public int gcd(int[] arr) {
int result = arr[0];
for(int i=1; i<arr.length; i++) {
result = getGcd(result, arr[i]);
}
return result;
}
public int getGcd(int a, int b) {
if(b == 0) return a;
return getGcd(b, a % b);
}
public List<Integer> getDivisors(int n) {
List<Integer> list = new ArrayList<>();
for(int i=1; i<=Math.sqrt(n); i++) {
if(n % i == 0) {
list.add(i);
if (i != n / i) {
list.add(n/i);
}
}
}
return list;
}
// 특정 숫자가 배열의 모든 원소를 나눌 수 있는지 확인
public boolean canDivideAll(int num, int[] arr) {
for(int now : arr) {
if(now % num == 0) return true;
}
return false;
}
}
[회고]
아래의 조건이 있었다. * 철수가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고 영희가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a * 영희가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고, 철수가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a
그리고, 마지막 문장에서 다음과 같은 글을 확인할 수 있었다. [주어진 조건을 만족하는 가장 큰 양의 정수 a를 return하도록 solution 함수를 완성해 주세요. 만약, 조건을 만족하는 a가 없다면, 0을 return 해 주세요.]
따라서, 최대공약수로 문제를 풀어야 함을 떠올렸고, 유클리드 호제법을 사용하여 문제를 풀이하였다.
유클리드 호제법은, 두 수의 최대공약수를 찾기 위한 알고리즘이다.
큰 수를 작은 수로 나누어 떨어지게 한 뒤, 이를 반복적으로 수행하여 나머지 0이 될 때까지 작동하는 방법을 의미한다.
최대 공약수는 흔히 GCD(Greatest Common Divisor)이라고 불린다.
1. 만약, 두 수 사이의 최대공약수를 구하려면 아래와 같이 코드를 작성하면 된다.
public static int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
2. 만약, 여러 수 중에서 최대공약수를 구한다면, 아래와 같이 코드를 작성하면 된다.
배열의 원소를 차례대로 순회하며 최대공약수를 계속 비교하는 방식이다.
public static int gcd(int[] arr) {
int result = arr[0];
for (int i = 1; i < arr.length; i++) {
result = getGcd(result, arr[i]);
}
return result;
}
public static int getGcd(int a, int b) {
if (b == 0) return a;
return getGcd(b, a % b);
}
이제, 다시 문제로 되돌아 가보자.
철수와 영희의 배열에서 각각의 최대 공약수를 구했으면, 이들의 약수를 구한 뒤, 조건을 만족하는 최대 값을 계산하면 된다.
최대공약수의 약수를 구할 때는 Math.sqrt를 이용하고, 그 값이 제곱근이 아닌 경우(값이 다른 경우)에만 리스트에 추가하여 중복처리를 하였다.
[참고]
최대 공약수 문제를 풀어본 김에, 최소 공배수는 어떻게 구하는지도 정리해보고자 한다.
최소 공배수는 흔히 LCM(Least Common Multiple)이라고 불린다.
public static int lcm(int a, int b) {
return a * b / gcd(a, b);
}
최대 공약수를 구할 때와 동일한 원리로, 여러 수 사이에서 최소 공배수를 구하려면 다음과 같이 작성하면 된다.
public static int lcm(int[] arr) {
int result = arr[0];
for (int i = 1; i < arr.length; i++) {
result = lcm(result, arr[i]);
}
return result;
}
public static int lcm(int a, int b) {
return (a * b) / gcd(a, b);
}