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

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

문제 설명

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

철수가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고 영희가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a
영희가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고, 철수가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 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, arrayB에서 동시에 포함하고 있는 약수 즉, 최대공약수를 각 배열마다 구해줘야 합니다. 배열에서 정수 두 개씩 for문을 통해 공통으로 나눠지는 수를 구하여 약수를 구하는 경우 시간 초과가 발생하므로 유클리드 호제법으로 최대공약수를 구해줍니다.

간단하게 유클리드 호제법이란 두 자연수 중 더 작은 값을 계속해서 더 큰 값으로 나눈 나머지를 구하는 과정을 거쳐 최대공약수를 구하는 알고리즘입니다.

유클리드 호제법 https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

각 배열에서 최대공약수 x, y를 구했으면 해당 수로 다른 배열의 원소를 하나라도 나술 수 있는지 없는지 확인하는 과정을 거쳐 나눌 수 없는 경우 두 조건을 만족하는 양의 정수 a의 후보가 됩니다.

풀이

import java.util.Arrays;

class Solution {
   public int solution(int[] arrayA, int[] arrayB) {
        int answer = 0;
        int n = arrayA.length;
        int m = arrayB.length;

        Arrays.sort(arrayA);
        Arrays.sort(arrayB);

        // 각 배열의 최대공약수 구하기
        int x = arrayA[0];
       
        for (int i = 1; i < n; i++) {
            x = gcd(arrayA[i], x);
        }

        int y = arrayB[0];
    
        for (int i = 1; i < m; i++) {
            y = gcd(arrayB[i], y);
        }
       
        // 다른 배열의 원소 중 하나라도 나눌 수 없는지 확인
        if (!divided(arrayB, x)) {
            answer = Math.max(answer, x);
        }

        if (!divided(arrayA, y)) {
            answer = Math.max(answer, y);
        }

        return answer;
    }

	// 유클리드 호제법(단, x > y)
    public int gcd(int x, int y) {	
        if (y == 0) {
            return x;
        } else {
            return gcd(y, x % y);
        }
    }


    public boolean divided(int[] arr, int a) {
        boolean divided = false;
        
        if (a <= 1) {
            return true;
        }
        
        int n = arr.length;
        
        for (int i = 0; i < n; i++) {
            if (arr[i] % a == 0) {
                divided = true;
            }
        }
        
        return divided;
    }
}

결과