링크

문제링크

문제

철수와 영희는 선생님으로부터 숫자가 하나씩 적힌 카드들을 절반씩 나눠서 가진 후, 다음 두 조건 중 하나를 만족하는 가장 큰 양의 정수 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	return
[10, 17]	[5, 20]	0
[10, 20]	[5, 17]	10
[14, 35, 119]	[18, 30, 102]	7

해결

arrayA 와 arrayB의 서로 상대 배열에서 안나누어지는 최대공약수를 찾는 문제이다.
일단 각자의 배열에서 모두 나누어지는 수를 찾기위해서 배열중 최솟값을 찾는다.
최솟값보다 큰 수는 배열의 모든수의 약수가 될수없다.

각 minA 와 minB까지 각 반복문에서 배열을 비교하면서 i의 약수 여부를 판별하여
각 배열의 조건에 만족하는 최대 공약수 maxA, maxB를 찾는다.

---

코드 개선
유클리드 호제법을 사용하여 배열의 최대공약수를 찾아서 두 공약수끼리 상대 배열에서 약수가 되는지 체크한 후 최대값을 찾는다.

배열의 최대공약수가 상대 배열의 약수가 되는경우
다른 나머지 약수들 모두 상대 배열의 약수가 된다는 점을 깨닫지 못했다.

최대공약수를 찾기만 하면되어서
부르트 포스 방식이었던 이전 코드보다는 최대공약수를 구하고 조건을 만족하는지 체크하는 방법이 훨씬 시간복잡도가 적기에 더 좋은 코드인것 같다.

코드

using System;

public class Solution {
    public int solution(int[] arrayA, int[] arrayB) {
        int answer = 0;
        int maxA = 0;
        int maxB = 0;
        
        // 각 배열에서 가장 작은값 찾기
        Array.Sort(arrayA);
        Array.Sort(arrayB);
        int minA = arrayA[0];
        int minB = arrayB[0];
        
        for (int i = 2; i <= minA; i++)
        {
            bool isDivisor = true;
            bool isNotDivisor = true;

            for (int j = 0; j < arrayA.Length; j++)
            {
                if (arrayA[j] % i != 0)
                {
                    isDivisor = false;
                    break;
                }

                if (arrayB[j] % i == 0)
                {
                    isNotDivisor = false;
                    break;
                }
            }

            if (isDivisor && isNotDivisor) 
            {
                maxA = i;
            }
        }
        
        for (int i = 2; i <= minB; i++)
        {
            bool isDivisor = true;
            bool isNotDivisor = true;

            for (int j = 0; j < arrayB.Length; j++)
            {
                if (arrayB[j] % i != 0)
                {
                    isDivisor = false;
                    break;
                }

                if (arrayA[j] % i == 0)
                {
                    isNotDivisor = false;
                    break;
                }
            }

            if (isDivisor && isNotDivisor) 
            {
                maxB = i;
            }
        }

        answer = Math.Max(maxA, maxB);
        
        return answer;
    }
}

// #######개선된 코드#########
using System;

public class Solution {
    public int solution(int[] arrayA, int[] arrayB) {
        int answer = 0;
        
        int gcdA = ArrayGcd(arrayA);
        int gcdB = ArrayGcd(arrayB);

        gcdA = CanDivisor(gcdA, arrayB) ? gcdA : 0;
        gcdB = CanDivisor(gcdB, arrayA) ? gcdB : 0;

        answer = Math.Max(gcdA, gcdB);        
        
        return answer;
    }
    
    private static int Gcd(int a, int b)
    {
        while (b != 0)
        {
            int tmp = a % b;
            a = b;
            b = tmp;
        }

        return a;
    }

    private static int ArrayGcd(int[] array)
    {
        int gcd = array[0];

        for (int i = 1; i < array.Length; i++)
        {
            gcd = Gcd(gcd, array[i]);
        }

        return gcd;
    }

    private static bool CanDivisor(int gcd, int[] array)
    {
        for (int i = 0; i < array.Length; i++)
        {
            if (array[i] % gcd == 0)
            {
                return false;
            }
        }

        return true;
    }
}