프로그래머스 - 숫자 카드 나누기

첫 번째 시도

import java.util.*;
import java.util.stream.*;

class Solution {
    
    public int solution(int[] arrayA, int[] arrayB) {
        int answer = 0;
        Arrays.sort(arrayA);
        Arrays.sort(arrayB);
        
        int numA = arrayA[0];
        int numB = arrayB[0];
        Set<Integer> setA = new HashSet<>();
        Set<Integer> setB = new HashSet<>();
        
        IntStream.rangeClosed(2,numA).filter(i -> numA % i == 0).forEach(i -> setA.add(i));
        IntStream.rangeClosed(2,numB).filter(i -> numB % i == 0).forEach(i -> {
            if (setA.contains(i)) {
                setA.remove(i);
            } else {
                setB.add(i);
            }
        });
              
        return Math.max(logic(arrayA,arrayB,setA), logic(arrayB,arrayA,setB));
    }
    
    private int logic(int[] arrayA , int[] arrayB,Set<Integer> set) {
        int answer = 0;
         for (int a : set) {
            if (check(arrayA,arrayB,a)) {
                answer = Math.max(a,answer);
            }
        }
        return answer;
    }
    
    private boolean check(int[] arrayA , int[] arrayB,int num) {
        for (int i=0;i<arrayA.length;i++) {
            if (arrayA[i] % num != 0 || arrayB[i]%num == 0)
                return false;
        }
        return true;
    }
}

첫 번째 시도는 위와 같습니다.
1. 각 배열에 대하여 먼저 정렬을 해줍니다.
2. 각 배열의 첫번째 값의 공약수를 구해주고 나서 set을 이용하여 공통된 공약수는 제거해줍니다.
3. 남은 공약수들을 이용하여 A배열이 나누어지면서 B배열이 나누어지지 않는지를 확인하고 성공하면 가장 큰 값을 정답값에 넣어줍니다. 반대도 같은 로직을 수행해줍니다.

통과는 했지만 시간이 꽤 많이 걸렸기에 구글에서 찾아본 결과 GCD를 활용하면 더욱 빠르고 편리하게 풀 수 있다는 것을 확인하였습니다.

두 번째 시도

import java.util.*;
import java.util.stream.*;

class Solution {
    
    public int solution(int[] arrayA, int[] arrayB) {
        int answer = 0;
        Arrays.sort(arrayA);
        Arrays.sort(arrayB);
        int gcda = arrayA[0];
        int gcdb = arrayB[0];
        
        for (int i=1;i<arrayA.length;i++) {
            gcda = gcd(gcda,arrayA[i]);
            gcdb = gcd(gcdb,arrayB[i]);
        }
        
        answer = logic(arrayA,gcdb) ? Math.max(answer,gcdb) : answer;
        answer = logic(arrayB,gcda) ? Math.max(answer,gcda) : answer;
        
        return answer;
    }
    
    private int gcd(int a,int b) {
        return b == 0 ? a :  gcd(b,a%b);
    }
    

    private boolean logic(int[] arr ,int num) {
        for (int i=0;i<arr.length;i++) {
            if (arr[i] % num == 0)
                return false;
        }
        return true;
    }
}

최대 공약수를 이용하여 푼 방법으로
1. 각 배열의 최대 공약수를 구합니다.
2. 해당 공약수를 이용하여 반대 배열에서 나누어 떨어지는 수가 있는지 확인 합니다. 만약 없다면 answer의 값을 gcd의 값과 비교하여 큰 값으로 변경해줍니다.

위와 같은 방법으로 푸니 속도가 훨씬 빨라진 것을 확인하였습니다.

참고자료 : 유튜브 - 숫자 카드 나누기