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

[문제]

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

 

 

[풀이]

 

먼저 두 벡터의 요소들에 대한 GCD를 구한다. 그리고 GCD가 1일 경우를 제외하고, 다른 벡터에서 구한 GCD를 요소에 대해 모두 나눠보는 시도를 진행한다. 이때 한 번도 나눠지지 않는다면 true가 되면서 조건을 만족하게 된다. 하지만 다른 벡터도 조건식을 통과하는지 검사하기 때문에, 두 벡터 모두 만족하는 수가 나올 수 있다. 이때는 가장 큰 값을 판별하기 위해 max를 활용하여 값 리턴하면 된다.

#include <string>
#include <vector>

using namespace std;

int GCD(int a, int b)
{
    while (b != 0)
    {
        int temp = a % b;
        a = b;
        b = temp;
    }

    return a;
}

int GetArrayGCD(const vector<int>& arr)
{
    int Result = arr[0];
    for (int i = 1; i < arr.size(); i++)
    {
        Result = GCD(Result, arr[i]);
    }
    return Result;
}

bool Try(const vector<int>& _Arr, int _GCD)
{
    if (1 == _GCD) return false;

    for (int val : _Arr)
    {
        if (val % _GCD == 0)
        {
            return false;
        }
    }

    return true;
}

// 다음 두 조건 중 하나를 만족하는 가장 큰 양의 정수 a의 값
// 1. arrayA는 모두 나눌 수 있고, arrayB는 모두 나눌 수 있는 수
// 2. arrayA는 모두 나눌 수 없고, arrayB는 모두 나눌 수 있는 수
int solution(vector<int> arrayA, vector<int> arrayB)
{
    int answer = 0;
    int AGcd = GetArrayGCD(arrayA);
    int BGcd = GetArrayGCD(arrayB);

    // 조건 1: A를 모두 나눌 수 있고, B를 하나도 나눌 수 없어야 함
    if (Try(arrayB, AGcd))
    {
        answer = max(answer, AGcd);
    }

    // 조건 2: B를 모두 나눌 수 있고, A를 하나도 나눌 수 없어야 함
    if (Try(arrayA, BGcd))
    {
        answer = max(answer, BGcd);
    }

    return answer;
}