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

 

두가지 풀이가 있다. 일단 첫번째 풀이에서는

'리스트에서의 최대공약수는, 리스트의 최솟값을 넘지 않는다' 라는 사실을 이용했다.

#include <string>
#include <vector>
#include <algorithm>
#define MAX(a, b) ((a >= b) ? a : b)

using namespace std;

int find(vector<int>& v1, vector<int>& v2, int min) {
    
    for(int i = min; i > 1; i--) {
        
        bool flag = true;
        
        for(auto v : v1) {
            
            if(v % i != 0) {
                flag = false;
                break;
            }
        }
        
        if(flag) {
            
            bool final = true;
            
            for(auto v : v2) {
                
                if(v % i == 0) {
                    final = false;
                    break;
                }
            }
            
            if(final)
                return i;   
        }
    }
    return 0;
}

int solution(vector<int> arrayA, vector<int> arrayB) {
    int answer = 0;
    
    // 각 리스트의 최대공약수는, 각 리스트의 최솟값을 넘지 않겠지요
    int minA = *min_element(arrayA.begin(), arrayA.end());
    int minB = *min_element(arrayB.begin(), arrayB.end());
    
    
    return MAX(find(arrayA, arrayB, minA), find(arrayB, arrayA, minB));
}

min_element를 처음 활용해보는 기회였다.

 

 

두번째는 GCD 함수를 구현하는 방식이다.

런타임 시간이 엄청나게 절약되었다.

#include <string>
#include <vector>
#define MAX(a, b) ((a > b) ? a : b)

using namespace std;

int gcd(int a, int b) {
    
    int temp;
    while(b != 0) {
        temp = a;
        a = b;
        b = temp % b;
    }
    return a;
}

int findValue(vector<int>& v1, vector<int>& v2, int size) {
        
    int gcdValue = v1[0];
    
    for(int i = 1; i < size; i++) {
        gcdValue = gcd(gcdValue, v1[i]);
        
        if(gcdValue == 1) return 0;
    }
    
    for(auto v : v2) {
        if(v % gcdValue == 0)
            return 0;
    }
    
    return gcdValue;
    
}

int solution(vector<int> arrayA, vector<int> arrayB) {
    int answer = 0;
    
    int size = arrayA.size();
    
    int a = findValue(arrayA, arrayB, size);
    int b = findValue(arrayB, arrayA, size);
    
    return MAX(a, b);
}