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

이 문제는 유클리드 호제법을 이용해서 푸는 문제이다. 배열의 최대 길이가 50만이므로, O(n) 알고리즘을 사용해서 풀어야 한다. 

 

철수나 영희가 가진 모든 숫자를 나눌 수 있고, 반대는 나눌 수 없는 가장 큰 수를 찾고, 없으면 0을 리턴하는 문제이다.

이 때 모든 숫자를 나눌 수 있다는 것에 집중했고, 그 중 가장 큰 수에 집중했다. 이 말이 곧 최대공약수를 나타내는 말이기 때문이다.

따라서 유클리드 호제법을 이용하여 gcd를 각각 구하고, 반대편의 배열에 루프를 돌며 나눌 수 있는지를 판단한다. 만약에 두 케이스 모두 나눌 수 있다면, 0을 리턴하도록 알고리즘을 구현했다. 최악의 경우에도 50만 + 50만 정도의 연산을 수행하므로, 1초 안에 문제가 풀린다.

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int gcd(int a, int b) {
    if (a < b) {
        swap(a, b);
    }
    
    if (b == 0) {
        return a;
    }
    
    return gcd(b, a % b);
}

int findGcd(vector<int>& arr) {
    int result = arr[0];
    
    int size = arr.size();
    for (int i = 1; i < size; i++) {
        result = gcd(result, arr[i]);
    }
    
    return result;
}

int indivisible(int number, vector<int>& target) {
    for (int temp : target) {
        if (temp % number == 0) {
            return 0;
        }
    }
    
    return number;
}

int solution(vector<int> arrayA, vector<int> arrayB) {
    int gcdA = findGcd(arrayA);
    int gcdB = findGcd(arrayB);
    
    int answer1 = indivisible(gcdA, arrayB);
    int answer2 = indivisible(gcdB, arrayA);
    
    return max(answer1, answer2);
}