프로그래머스 숫자 카드 나누기 [Lv. 2] (C++)

프로그래머스

철수와 영희가 가진 각각의 숫자를 입력받을 때, 한 명이 가진 모든 숫자를 나눌 수 있고, 다른 한 명이 가진 모든 숫자를 나눌 수 없는 수를 찾아주세요. (해당되는 숫자가 여러 개라면 가장 큰 수를 반환)

 

 

풀이 방법

최대 공약수를 찾는 문제입니다. 유클리드 호제법을 이용하여 최대 공약수를 찾아줘야합니다.

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

 

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

 

각 배열의 최대 공약수를 유클리드 호제법을 통해 빠르게 찾아줍니다.

int gcdA = arrayA[0];
int gcdB = arrayB[0];

for (int n : arrayA)
    gcdA = gcd(gcdA, n);

for (int n : arrayB)
    gcdB = gcd(gcdB, n);

 

 

앞서 찾은 최대 공약수가 다른 배열에도 적용이 되는 수인지 체크합니다. 만약 나뉘는 수가 있다면 -1로 바꿔줍니다.

for (int i = 0; i < arrayA.size(); i++)
{
    if (arrayA[i] % gcdB == 0)
        gcdB = -1;
}

for (int i = 0; i < arrayB.size(); i++)
{
    if (arrayB[i] % gcdA == 0)
        gcdA = -1;
}

 

 

둘 중 더 큰 수를 반환해 줍니다. 둘 다 -1이라면 해당되는 수가 없다는 의미이니 0을 반환합니다.

int answer = max(gcdA, gcdB);
return max(answer, 0);

 

 

정답 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

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

int solution(vector<int> arrayA, vector<int> arrayB) 
{
    int gcdA = arrayA[0];
    int gcdB = arrayB[0];
    
    for (int n : arrayA)
        gcdA = gcd(gcdA, n);
    
    for (int n : arrayB)
        gcdB = gcd(gcdB, n);
    
    for (int i = 0; i < arrayA.size(); i++)
    {
        if (arrayA[i] % gcdB == 0)
            gcdB = -1;
    }
    
    for (int i = 0; i < arrayB.size(); i++)
    {
        if (arrayB[i] % gcdA == 0)
            gcdA = -1;
    }
    
    int answer = max(gcdA, gcdB);

    return max(answer, 0);
}