프로그래머스 (C/C++) 135807 : 숫자 카드 나누기 (2)

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

프로그래머스

 

 

---

풀이

각 배열을 순회하며 최대공약수를 구한 후, 각 배열의 공약수로 다른 배열을 순회하며 나눠지는 수가 있는지 판단 후 큰 걸 반환했다.

다른 배열을 순회하며 나누어지는 수가 없는 경우에만 answer에 값을 저장하여 반환값을 비교했다.

---

코드

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

int getGCD(int a, int b) {
    if (b == 0)
        return a;
    return getGCD(b, a % b);
}

int solution(vector<int> arrayA, vector<int> arrayB) {
    int gcdA = arrayA[0], gcdB = arrayB[0];
    int answer = 0;
    
    // 각 배열의 최대공약수 구하기
    for (int i = 1; i < arrayA.size(); i++)
        gcdA = getGCD(gcdA, arrayA[i]);
    
    for (int i = 1; i < arrayB.size(); i++)
        gcdB = getGCD(gcdB, arrayB[i]);
    
    // A 배열의 원소가 gcdB로 나눠지는지, B 배열의 원소가 gcdA로 나눠지는지 확인
    int i;
    for (i = 0; i < arrayA.size(); i++) {
        if (arrayA[i] % gcdB == 0) break;
    }
    if (i == arrayA.size())
        answer = gcdB;
    
    for (i = 0; i < arrayB.size(); i++) {
        if (arrayB[i] % gcdA == 0) break;
    }
    if (i == arrayB.size())
        answer = max(gcdA, answer);
    
    return answer;
}