[JAVA] 배열의 최대공약수 계산

오늘의 학습 키워드

• 최대공약수 (GCD) 계산
• 배열의 최대공약수
• 조건을 만족하는 가장 큰 양의 정수 찾기
• 유클리드 알고리즘

공부한 내용 본인의 언어로 정리하기

오늘의 문제 : 숫자 카드 나누기 

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

class Solution {
    public int solution(int[] arrayA, int[] arrayB) {
        // 1번 조건 - 배열의 최대 공약수
        int gcdA = gcdOfArray(arrayA);
        int gcdB = gcdOfArray(arrayB);
        
        // 2번 조건 - 다른 배열을 하나도 나눌 수 없는지 확인
        int candidateA = isValid(arrayB, gcdA) ? gcdA : 0;
        int candidateB = isValid(arrayA, gcdB) ? gcdB : 0;
        
        return Math.max(candidateA, candidateB);
    }
    
    // 카드들에 적힌 모든 숫자를 나눌 수 있는 수 -> 배열의 최대 공약수
    private int gcdOfArray(int[] array) {
        int gcd = array[0];
        
        for (int num : array) {
            gcd = gcd(gcd, num);
        }
        
        return gcd;
    }
    
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        
        return a;
    }
    
    private boolean isValid(int[] array, int gcd) {
        for (int num : array) {
            if (num % gcd == 0) {
                return false;
            }
        }
        
        return true;
    }
}

 

두 배열이 주어졌을 때, 각각의 배열의 최대공약수를 구하고, 그 값이 다른 배열의 원소를 나눌 수 있는지 없는지를 확인하는 문제를 공부했습니다. 주요한 포인트는 각 배열의 최대공약수를 구한 후, 이를 다른 배열의 원소와 비교하는 것이었습니다. 이를 위해 최대공약수를 구하는 함수와 조건을 확인하는 함수를 작성했습니다. 

오늘의 회고

어떤 문제가 있었고, 나는 어떤 시도를 했는지

• 문제: 주어진 두 배열에서 최대공약수를 구한 후, 해당 최대공약수가 다른 배열의 원소를 나누지 않는 가장 큰 값을 찾아야 했습니다.
• 시도: 먼저 두 배열의 최대공약수를 구하고, 이를 바탕으로 각 조건을 만족하는 값을 찾는 코드를 작성했습니다. 유클리드 알고리즘을 사용하여 최대공약수를 효율적으로 구할 수 있다는 것을 알고 있어서 코드를 바로 짜기 시작했지만, gcd 함수에서 ArithmeticException: / by zero 오류가 발생했습니다. 반환 값이 0이 되지 않도록 수정해봤지만 해결하지 못했습니다. 

어떻게 해결했는지

• 구글링을 통해 a를 b로 나눈 나머지를 b에 할당한 후 이전에 저장한 temp 값을 a에 할당하지 않고, b에 할당했다는 사실을 알게 되었습니다. a에 temp 값을 할당함으로써 이전의 b 값으로 업데이트합니다.

무엇을 새롭게 알았는지

• 두 배열의 최대공약수를 각각 구한 후, 다른 배열에서 해당 값을 나눌 수 없는지 확인하는 방법이 문제 해결의 핵심이라는 점을 깨달았습니다.

내일 학습할 것은 무엇인지

• 내일의 문제를 또 풀어봅시다!