[프로그래머스] Lv2. 숫자 카드 나누기(Java)

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

프로그래머스

---

문제

문제 설명

철수와 영희는 선생님으로부터 숫자가 하나씩 적힌 카드들을 절반씩 나눠서 가진 후, 다음 두 조건 중 하나를 만족하는 가장 큰 양의 정수 a의 값을 구하려고 합니다.

1. 철수가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고 영희가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a
2. 영희가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고, 철수가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a

예를 들어, 카드들에 10, 5, 20, 17이 적혀 있는 경우에 대해 생각해 봅시다. 만약, 철수가 [10, 17]이 적힌 카드를 갖고, 영희가 [5, 20]이 적힌 카드를 갖는다면 두 조건 중 하나를 만족하는 양의 정수 a는 존재하지 않습니다. 하지만, 철수가 [10, 20]이 적힌 카드를 갖고, 영희가 [5, 17]이 적힌 카드를 갖는다면, 철수가 가진 카드들의 숫자는 모두 10으로 나눌 수 있고, 영희가 가진 카드들의 숫자는 모두 10으로 나눌 수 없습니다. 따라서 철수와 영희는 각각 [10, 20]이 적힌 카드, [5, 17]이 적힌 카드로 나눠 가졌다면 조건에 해당하는 양의 정수 a는 10이 됩니다.

철수가 가진 카드에 적힌 숫자들을 나타내는 정수 배열 arrayA와 영희가 가진 카드에 적힌 숫자들을 나타내는 정수 배열 arrayB가 주어졌을 때, 주어진 조건을 만족하는 가장 큰 양의 정수 a를 return하도록 solution 함수를 완성해 주세요. 만약, 조건을 만족하는 a가 없다면, 0을 return 해 주세요.

제한사항

 

• 1 ≤ arrayA의 길이 = arrayB의 길이 ≤ 500,000
• 1 ≤ arrayA의 원소, arrayB의 원소 ≤ 100,000,000
• arrayA와 arrayB에는 중복된 원소가 있을 수 있습니다.

입출력 예

---

풀이

접근방법

arrayA or arrayB에서는 전부 나눠지는 수를 구해야 한다는 점에서 최대공약수를 생각했습니다.

arrayA의 최대공약수인 gcdA를 구하고, gcdA가 arrayB에서 나눠지는 수가 하나라도 있다면, gcdA의 약수로 나눈다고 해도 최대공약수로 나눠지는 수는 무조건 나눠질 것입니다. 따라서 각 배열의 최대공약수를 구하고 다른 배열에서 나눠지는 지 확인하면 됩니다.

 

풀이

최대공약수를 구하는 함수 gcd와 하나도 나눠지지 않는지 확인하는 함수 cantDivide를 만들었습니다.

 

gcd는 유클리드 호제법을 사용해서 구했습니다.

유클리드 호제법은 a로 b를 나눈 나머지가 r일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 성질을 활용한 최대공약수를 구하는 방법입니다. 

이 성질은 재귀적으로 이뤄질 수 있는데, num1과 num2의 최대공약수를 구한다고 할 때 num2와 num1%num2의 최대공약수를 구하는 것과 같습니다. 나머지가 0이 되면 나눠떨어진다는 의미(→ 약수)이기 때문에 나누는 수가 최대공약수가 됩니다.

int gcd(int num1, int num2){
    if (num2 == 0) return num1;
    return gcd(num2, num1%num2);
}

주의해야 할 점은 num1 > num2 일 때 유클리드 호제법을 사용해서 gcd를 구할 수 있기 때문에 arrayA와 arrayB를 sort 해줍니다.

 

 

cantDivide 함수는 divisor가 배열 arr를 전부 나눌 수 없는지를 확인하는 함수입니다.

arr를 돌면서 divisor로 나눠떨어지는 수가 하나라도 있다면 false를 return, 아니라면 true를 return 합니다.

 

arrayA의 최대공약수 gcdA를 구한 뒤 arrayB가 gcdA로 나눠지지 않는 지 확인합니다. 나눠지지 않는다면 answer에 gcdA를 저장합니다. 똑같이 arrayB에 대해서도 최대공약수 gcdB를 구한 뒤 arrayA가 gcdB로 나눠지지 않는지 확인하고, 나눠지지 않는다면 answer와 gcdB 중 더 큰 값을 answer에 저장합니다.

 

주의할 점은 arrayA, arrayB의 최대공약수를 구할 때, 배열의 길이가 1이라면 배열에 들어있는 값이 최대공약수가 되기 때문에 arrayA[0]과 arrayB[0]이 초기값이 되고, 1부터 배열의 길이만큼 gcd를 구해야 합니다.

---

소스코드

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];
        for(int i=1; i<arrayA.length; i++){
            gcdA = gcd(arrayA[i], gcdA);
        }
        
        if(cantDivide(gcdA, arrayB)) answer = gcdA;
        
        int gcdB = arrayB[0];
        for(int i=1; i<arrayB.length; i++){
            gcdB = gcd(arrayB[i], gcdB);
        }
        
        if(cantDivide(gcdB, arrayA)) answer = Math.max(answer, gcdB);
        
        return answer;
    }
    
    // num1 > num2 일때 gcd 구하기
    int gcd(int num1, int num2){
        if (num2 == 0) return num1;
	    return gcd(num2, num1%num2);
    }
    
    // divisor로 arr를 모두 나눌 수 없는지 확인
    boolean cantDivide(int divisor, int[] arr){
        for(int num : arr){
            if(num % divisor == 0) return false;
        }
        
        return true;
    }
}