[Algorithm] 프로그래머스 - 숫자 카드 나누기 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

 

이번 포스팅은 프로그래머스 - 숫자 카드 나누기 문제 해결에 대한 글을 작성하도록 하겠습니다.

 

문제 소스: https://school.programmers.co.kr/learn/courses/30/lessons/135807

프로그래머스

 

 

1. 풀이 소스

 

//14:49 

class Solution {
    public int solution(int[] arrayA, int[] arrayB) {
        // 나눌 수 있다 = 정수로 약분 가능 = A는 gcdA의 배수이다 
        
        int gcdA = findGCD(arrayA); // A 최대 공약수 찾기
        int gcdB = findGCD(arrayB);
        
        if (gcdA == gcdB) return 0; // 만약 두 최대 공약수가 같다면 어떻게든 두 배열에서 하나 원소 이상씩은 나눠짐
        
        boolean isGCDA = isGCD(gcdA, arrayB); // A배열의 최대 공약수로 B 배열을 나눌 수 있는지 판단
        boolean isGCDB = isGCD(gcdB, arrayA);
        
        if (!isGCDA && !isGCDB) return gcdA <= gcdB ? gcdB : gcdA; // 둘 다 가능한 경우 (false) 더 큰 수
        else if (!isGCDA) return gcdA; // 만약 gcdA만 arrayB의 원소를 나눌 수 없는 경우
        else if (!isGCDB) return gcdB;
       
        return 0;
    }
    
    
    int findGCD(int[] arr) { // 배열에서 공통된 최대 공약수 찾기
        int gcd = arr[0]; // 첫번째 원소
        
        for (int num : arr) {
            gcd = getGCD(gcd, num);
        }
        
        return gcd;
    }
    
    int getGCD(int x, int y) { // 유클리드 호제법으로 최대 공약수 찾기
        if (y == 0) return x;        
        return getGCD(y, x % y);
    }
    
    boolean isGCD(int gcd, int[] arr) { // 찾은 최대 공약수가 배열에서 나뉘어 지는지
        for (int num : arr) {
            if (num % gcd == 0) return true; 
        }
        
        return false;
    }

}

 

 

2. 풀이 과정

 

해당 문제는 최대 공약수를 찾는 과정이 key였습니다. 최대 공약수는 재귀로 해결할 수 있습니다.

 

int getGCD(int x, int y) {
    if (y == 0) return x;
    else getGCD(y, x % y);
}

 

만약 getGCD(4, 2)를 입력할 경우 시뮬에이션은 다음과 같습니다.

 

getGCD(4, 2)

= getGCD(2, 4 % 2)

= getGCD(2, 0)

 

y == 0 : return x => 2

따라서, return 2

 

이러한 방식으로 배열 원소에 대한 공통의 최대 공약수를 찾은 후, gcdA는 arrayB, gcdB는 arrayA에 적용하여 나눌 수 있는지 파악하는 것이 중요하였습니다.

 

이상으로 프로그래머스 숫자 카드 나누기 자바 문제를 마치도록 하겠습니다.

 

감사합니다.!