프로그래머스 숫자카드나누기 // 복잡하면 함수로.. , 배열을 정렬하라.

코딩테스트 연습 - 숫자 카드 나누기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

문제 : 탐색이많다

해결 : 정렬, 배열중 최소값의 약수 비교만으로 충분함. 

ex) 14,35, 70 의 최대공약수 후보 : 1,7,14 중에 있다. / 35,70약수는 필요없음.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

//안나눠 지는게 잇다.(true)
bool is_rest (int num, vector<int> array)
{
    for(auto c : array) if (c%num) return true;
    return false;
}

//나눠 지는게 잇다.(true)
bool is_norest(int num, vector<int> array)
{
    for(auto c : array) if (c%num==0) return true;
    return false;
}

int func(int n, vector<int> array, vector<int> compare)
{//n은 해당 배열의 가장 최소값, array 해당 배열, compare 다른 배열
    for (int i = n; i > 1; i--)
    {//해당 배열에서 조건에 만족하는 가장 큰 약수만을 필요로 하기 때문에
        if (n % i == 0)
        {//약수이면
            if(is_rest(i, array)) continue;//안나눠지는게 잇으면 패스
            if(is_norest(i, compare)) continue;//나눠 지는게 잇으면 패스
            return i;
        }
    }
    return 0;
}

int solution(vector<int> arrayA, vector<int> arrayB)
{
    sort(arrayA.begin(), arrayA.end());//오름차순 정렬(가장 작은값을 기준으로 할것이기 때문)
    sort(arrayB.begin(), arrayB.end());//마찬가지
    //func을 돌린 값중 큰값 리턴
    return max(func(arrayA[0], arrayA, arrayB), func(arrayB[0], arrayB, arrayA));
}