[Programmers] 숫자 카드 나누기 / ⭕

 

프로그래머스

 

1. 제출 코드 (26분 24초 / 유클리드 호제법)

class Solution {
    public int solution(int[] arrayA, int[] arrayB) {
        int answer = 0;
        int tempA = arrayA[0];
        int tempB = arrayB[0];
        for(int i = 1; i < arrayA.length; i++) {
            tempA = gcd(tempA, arrayA[i]);
            tempB = gcd(tempB, arrayB[i]);
        }

        for(int i = 0; i < arrayB.length; i++) {
            if(arrayB[i] % tempA == 0) {
                tempA = 0;
                break;
            }
        }
        for(int i = 0; i < arrayB.length; i++) {
            if(arrayA[i] % tempB == 0) {
                tempB = 0;
                break;
            }
        }
        answer = Math.max(tempA, tempB);
        return answer;
    }
    
    static public int gcd(int a, int b) {
        if(b == 0){
            return a;
        } else {
            return gcd(b, a % b);
        }
    }
}

 

2. 구현 로직

1. 가장 큰 양의 정수 A값을 구하는 것이므로 최대공약수를 구해야겠다고 생각했다. 또, array의 길이가 500,000으로 시간복잡도가 N^2이상이면 안될 거 같아서 유클리드 호제법을 이용했다.
2. 첫번째 경우에서 a를 구하기 위해 arrayA의 최대공약수를 구하고 arrayB에서 나머지 연산을 수행했다.
3. 두번째 경우에서 a를 구하기 위해 arrayB의 최대공약수를 구하고 arrayA에서 나머지 연산을 수행했다.
4. 두개의 a를 비교해서 정답을 추출했다.

 

3. 유의할 점

• 시간복잡도를 고려해서 유클리드 호제법을 사용해야될 거 같다.