[Java] Lv.2 숫자 카드 나누기

문제

문제 풀이

두 배열 중 한 배열은 한 값에 나누어떨어지고 한 배열은 안되는 경우 중 가장 큰 수를 뽑는 문제.

생각해보면 정답은 한 배열의 가장 작은 수 보다 클 수가 없다. ( 더 크다면 그 값은 가장 작은 수로 무조건 나눌 수가 없다)

그래서 확인은 두 배열의 가장 작은 값 두 개를 활용하여 풀면 된다.

여기서 그 두 값만 확인한다고 끝이 아니라 각 수의 약수들도 확인을 해주어야한다.

가장 작은 두 값은 조건을 만족하지 않는데 해당 두 수의 각 약수 중 하나가 조건을 만족하는 경우 해당 값이 정답이 되기 때문이다. 

즉, 1. A배열의 가장 작은 수의 약수가 A배열을 다 나눌 수 있고 B배열을 다 못나누는 경우

2. B배열의 가장 작은 수의 약수가 B배열을 다 나눌 수 있고 A배열을 다 못나누는 경우

이 두 가지를 확인하면 된다.

자바 코드

import java.util.*;

class Solution {
    private List<Integer> list;
    public int solution(int[] arrayA, int[] arrayB) {
        int answer = 0;
        
        // 배열들 오름차순 정렬
        Arrays.sort(arrayA);
        Arrays.sort(arrayB);
        
        // A는 나누어지고 B는 못나누는 수 구하기
        answer = findAnswer(arrayA, arrayB);
        // B는 나누어지고 A는 못나누는 수 구한 뒤 이전 answer와 비교하여 더 큰 값 저장
        answer = Math.max(answer, findAnswer(arrayB, arrayA));
        
        return answer;
    }
    
    // 한 배열에서 조건을 만족하는 값 찾기
    public int findAnswer(int[] a, int[] b){
        // a배열의 가장 작은 값의 약수 찾기
        findDivide(a[0]);
        
        // 약수를 내림차순으로 정렬
        Collections.sort(list, Collections.reverseOrder());
        
        // 큰 값부터 배열을 나누어 확인한다.
        for(int i : list){
            // a 배열은 나누어지고 b 배열은 안나누어지면 해당 i값 반환
            if(canDivide(a, i) && cantDivide(b, i))
                return i;
        }
        
        // 조건을 만족하지 못하면 0반환
        return 0;
    }
    
    // 배열이 특정 약수에 나누어지는 지 확인하는 메소드
    public boolean canDivide(int[] arr, int divide){
        // 배열의 값 중 하나라도 약수에 나누어떨어지지 않으면 false 반환
        for(int i : arr){
            if(i % divide != 0)
                return false;
        }
        
        return true;
    }
    
    // 배열이 특정 약수에 나누어지지 않는지 확인하는 메소드
    public boolean cantDivide(int[] arr, int divide){
        // 배열의 값 중 하나라도 약수에 나누어떨어지면 false 반환
        for(int i : arr){
            if(i % divide == 0)
                return false;
        }
        
        return true;
    }
    
    // 특정 값의 약수를 찾는 메소드
    public void findDivide(int num){
        list = new ArrayList<>();
        
        for(int i = 2; i * i <= num; i++){
            if(num % i == 0){
                list.add(i);
                list.add(num / i);
            }
        }
        
        list.add(num);
    }
}