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

문제

---

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

풀이

---

#include <iostream>
#include <string>
#include <vector>
#include <string>
#include <stack>
#include <cmath>
#include <algorithm> 
#include <map>

using namespace std;

//동시에 체크하는 것이 유리함
//가장 큰 수가 될 수 있는 최대 값은 두 배열의 최소 값 중 더 큰 값이 됨

void searchDivisors(vector<int> &divisors, int dividend, int notDividend)
{
    vector<int> temp = {};

    for (int i = 0; i < divisors.size(); i++)
    {
        if (!(dividend % divisors[i] != 0 || notDividend % divisors[i] == 0))
        {
            temp.push_back(divisors[i]);
        }
    }
    divisors = temp;
}

int solution(vector<int> arrayA, vector<int> arrayB)
{
    int answer = 0;

    // arrayA의 모든 원소를 나눌 수 있지만, arrayB의 모든 원소를 나눌 수 없는 양의 정수
    // arrayB의 모든 원소를 나눌 수 있지만, arrayA의 모든 원소를 나눌 수 없는 양의 정수
    // 두 양의 정수 중 최댓값
    // 조건 충족 X -> return (int) 0

    //이를 만족하는 최대값은 각 배열의 최솟값
    sort(arrayA.begin(), arrayA.end());
    sort(arrayB.begin(), arrayB.end());


    //최솟값의 약수를찾고 이를 앞에서부터 비교해나가면서 약수를 줄인다.
    vector<int> divisorsA = {};
    vector<int> divisorsB = {};

    //둘다 만족하는 경우는 정답이 될수 없으므로, 이를 제외
    for (int i = 2; i <= max(arrayA[0], arrayB[0]); i++)
    {
        if (!(arrayA[0] % i == 0 && arrayB[0] % i == 0))
        {
            if (arrayA[0] % i == 0) divisorsA.push_back(i);
            else if (arrayB[0] % i == 0) divisorsB.push_back(i);
        }
    }

    for (int i = 0; i < arrayA.size(); i++)
    {
        searchDivisors(divisorsA, arrayA[i], arrayB[i]);
        searchDivisors(divisorsB, arrayB[i], arrayA[i]);
    }

    int maxA = 0;
    int maxB = 0;

    if(!(divisorsA.size() == 0)) maxA = *max_element(divisorsA.begin(), divisorsA.end());
    if (!(divisorsB.size() == 0)) maxB = *max_element(divisorsB.begin(), divisorsB.end());

    answer = max(maxA, maxB);

    return answer;
}