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

문제

 

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

프로그래머스

 

문제풀이

카드들에 적힌 모든 숫자를 나눌 수 있는 숫자는 최대공약수를 의미한다.

 

배열 A의 최대공약수를 구해 배열 B의 원소들을 나눌 때 나누어지지 않는 숫자를 구한다.

배열 B도 마찬가지로 최대공약수를 구해 배열 A원소들을 나눌 때 나누어지지 않은 숫자를 구한다.

두 숫자 중 큰 값을 반환하면 된다.

 

만약 최대공약수로 나누어지는 숫자가 있으면 해당 a값은 0이 된다.

 

int getGCD(int num1, int num2) {
    int num3(0);
    while (num2 > 0) {
        num3 = num1 % num2;
        num1 = num2;
        num2 = num3;
    }
    return num1;
}

최대공약수를 구하는 함수이다.

두 숫자를 입력받고 유클리드 호제법을 이용하여 두 수의 최대공약수를 구한다.

 

int getNum(vector<int>A, vector<int>B) {
    int num(0);
    if (A.size() == 1) num = A[0];
    else num = getGCD(A[0], A[1]);

    for (int idx = 2; idx < A.size(); ++idx) num = getGCD(num, A[idx]);

    bool canDiv(false);
    for (int idx = 0; idx < B.size(); ++idx) {
        if (B[idx] % num == 0) {
            canDiv = true;
            break;
        }
    }

    if (canDiv == false) return num;
    else return 0;
}

문제에서 구하려는 양의 정수 a를 구하는 함수이다.

두 벡터를 입력받고 A의 최대공약수를 구해 B의 원소들을 최대공약수로 나눌 때 나누어 떨어지지 않으면 최대공약수를 반환, 하나라도 나누어 떨어진다면 0을 반환한다.

 

벡터의 원소가 하나일 때는 최대공약수가 해당 수가 된다.

 

코드

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

int getGCD(int num1, int num2) {
    int num3(0);
    while (num2 > 0) {
        num3 = num1 % num2;
        num1 = num2;
        num2 = num3;
    }
    return num1;
}

int getNum(vector<int>A, vector<int>B) {
    int num(0);
    if (A.size() == 1) num = A[0];
    else num = getGCD(A[0], A[1]);

    for (int idx = 2; idx < A.size(); ++idx) num = getGCD(num, A[idx]);

    bool canDiv(false);
    for (int idx = 0; idx < B.size(); ++idx) {
        if (B[idx] % num == 0) {
            canDiv = true;
            break;
        }
    }

    if (canDiv == false) return num;
    else return 0;
}

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

    answer = max(getNum(arrayA, arrayB), getNum(arrayB, arrayA));

    return answer;
}