[프로그래머스/Lv. 2] 숫자 카드 나누기 (JAVA)

🔺 문제

프로그래머스

 

 

🔺 코드

import java.util.*;
 
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(arrayA[i], gcdA);
            gcdB = gcd(arrayB[i], gcdB);
        }
        
        if(!canDivide(arrayB, gcdA)) { // 나눌 수 없을 때, 최댓값 비교해 갱신
            answer = Math.max(answer, gcdA);
        }
        
        if(!canDivide(arrayA, gcdB)) {
            answer = Math.max(answer, gcdB);
        }
        
        return answer;
    }
    
    // 약수 구하기 (유클리드 호제법)
    private static int gcd(int a, int b) {
        if(b == 0)  return a;
        return gcd(b, a % b);
    }
    
    // 약수로 해당 배열 내 원소들이 나눠지는지 구하기
    private static boolean canDivide(int[] arr, int gcd) {
        for(int i : arr) {
            if(i % gcd == 0)
                return true;
        }
        return false;
    }
}

 

 

 

🧩  해결 아이디어

- arrA에서 최대공약수 구하고, arrB 내 원소들이 이 값으로 나눠지는지 구하기
- arrB에서 최대공약수 구하고, arrA 내 원소들이 이 값으로 나눠지는지 구하기

 

- 해당 값으로 나눌 수 없다면, 최댓값과 비교해 갱신한다.

 

 

---

💬 느낀 점

해결 아이디어는 생각했는데

첨에 약수 구하기를 일일이 숫자 비교하면서 해가지고 시간초과가 떴었다....

약수 구하기 유클리드 호제법 잊지 말자...

가끔 쓰면 꼭 까먹는ㅠ

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[pro] 프로그래머스 level2 135807 숫자 카드 나누기 (Java) - 시뮬레이션