[프로그래머스][Java][Lv. 2] 숫자 카드 나누기

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/135807

 

---

 

제한 사항

 

---

 

입출력 예

 

---

 

풀이

class Solution {
    public int solution(int[] arrayA, int[] arrayB) {       
        int aMax = arrayA[0], bMax = arrayB[0];
        for (int i = 1; i < arrayA.length; i++) {
            aMax = gcd(aMax, arrayA[i]);
        }
        for (int i = 1; i < arrayB.length; i++) {
            bMax = gcd(bMax, arrayB[i]);
        }
        
        boolean aCheck = true, bCheck = true;
        for (int a : arrayA) {
            if (a % bMax == 0) {
                bCheck = false;
                break;
            }
        }
        for (int b : arrayB) {
            if (b % aMax == 0) {
                aCheck = false;
                break;
            }
        }
        
        if (aCheck && bCheck) return Math.max(aMax, bMax);
        else if (aCheck) return aMax;
        else if (bCheck) return bMax;
        else return 0;
    }
    
    private int gcd(int i, int j) {
        if (j == 0) return i;
        else return gcd(j, i % j);
    }
}

 

---

 

후기

최대 공약수를 구해야 하는거 같아서 처음에 약수 구하는 방법으로 Set을 이용해서 구현해 봤는데 틀리지는 않지만 실행 시간이 너무 오래 걸려서 통과하지 못했다. 그래서 도대체 어떻게 하나 찾아봤는데 최대 공약수를 구하는 공식인 유클리드 호제법이 있었다. 그걸 사용했더니 바로 통과했다. 이 방법 말고 그냥 단순히 일일이 비교해서 구하는 방법도 있는거 같은데 그렇게 하면 뭔가 의미가 없는거 같아서 일부러 새로운 내용을 배울 겸 이렇게 풀었다.