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

프로그래머스

 

• arrayA의 카드들에 적힌 모든 숫자를 나눌 수 있고, arrayB의 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a 
• arrayB의 카드들에 적힌 모든 숫자를 나눌 수 있고, arrayA의 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a

 

• 위 둘 중 하나를 만족하는 가장 큰 양의 정수 a를 구해야 함
• 특정 카드들에 적힌 모든 숫자를 나눌 수 있음 => 최대공약수
• 한 쪽의 최대 공약수를 구해서 다른 한 쪽을 나눌 수 없는지 체크 후 양측에 각각 해당하는 값이 있다면 더 큰 값을 리턴

 

> arrayA의 최대공약수를 구하고 해당 값이 arrayB를 나눌 수 있는지 체크 후 나눌 수 없다면 answer 값과 비교해서 크다면 저장

> arrayB의 최대공약수를 구하고 해당 값이 arrayA를 나눌 수 있는지 체크 후 나눌 수 없다면 answer 값과 비교해서 크다면 저장

 

#include <string>
#include <vector>

using namespace std;

// 최대 공약수
int gcd(int a, int b) {
    if(b == 0) return a;
    return gcd(b, a%b);
}

// 값 비교
int compare(int a, int b) {
    if(a > b) return a;
    return b;
}

int solution(vector<int> arrayA, vector<int> arrayB) {
    int answer = 0;
    int length = arrayA.size();
    
    // arrayA의 최대공약수 구하기
    int gcdValue = arrayA[0];
    
    for(int i = 1 ; i < length; i++) {
        gcdValue = gcd(gcdValue, arrayA[i]);
        if(gcdValue == 1) break;
    }
    
    // 최대공약수가 1이면 패스
    if(gcdValue != 1) {
        int cnt = 0;
        
        // arrayB에 나눌 수 있는 값이 있는지 체크
        for(int i = 0; i < length; i++) {
            if(arrayB[i] % gcdValue == 0) break;    
            cnt++;
        }
        
        //cnt == length면 answer = 최대공약수
        if(cnt == length) answer = gcdValue;
    }
    
    // arrayB의 최대공약수 구하기
    gcdValue = arrayB[0];
    
    for(int i = 0; i < length; i++) {
        gcdValue = gcd(gcdValue, arrayB[i]);
        if(gcdValue == 1) break;
    }
    
    // 최대공약수가 1이면 패스
    if(gcdValue != 1) {
        int cnt = 0;
        
        // arrayA에 나눌 수 있는 값이 있는지 체크
        for(int i = 0; i < length; i++) {
            if(arrayA[i] % gcdValue == 0) break;
            cnt++;
        }
        
        //cnt == length면 answer와 비교해서 더 큰 놈을 answer에 저장
        if(cnt == length) answer = compare(answer, gcdValue);
    }
    
    return answer;
}