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

 

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

 

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

프로그래머스

---

 

해결전략

 

최대 공약수 GCD

수학, 구현

---

 

정답코드 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
// 유클리드 호제법을 사용하여 GCD를 찾음
int gcd(int a, int b){
    if (b == 0) 
        return a;
 
    return gcd(b, a % b); 
}
 
int solution(vector<int> arrA, vector<int> arrB) {
    
    int x = arrA[0]; 
    for(int i = 1; i < arrA.size(); i++){ 
        x = gcd(x, arrA[i]); // 현재까지의 GCD와 다음 요소의 GCD를 계산
    }
 
    int y = arrB[0]; 
    for (int i = 1; i < arrB.size(); i++) { 
        y = gcd(y, arrB[i]); // 현재까지의 GCD와 다음 요소의 GCD를 계산
    }
 
    // x와 y 사용 가능 여부를 나타내는 플래그
    bool useX = true;
    bool useY = true;
 
    if (x == 1 && y == 1) return 0; // GCD가 둘 다 1인 경우, 공통된 소수를 가지지 않으므로 0 반환
    else if (x > 1 && y == 1)
    {        
        for (int i = 0; i < arrB.size(); i++) // arrB 내부의 모든 요소가 x로 나누어 떨어지지 않으면 x 반환
        {
            if (arrB[i] % x == 0) return 0; // 나누어 떨어지면 0 반환
        }
        return x; 
    }
    else if (x == 1 && y > 1)
    {
        for (int i = 0; i < arrA.size(); i++) // arrA 내부의 모든 요소가 y로 나누어 떨어지지 않으면 y 반환
        {
            if (arrA[i] % y == 0) return 0; // 나누어 떨어지면 0 반환
        }
        return y;
    }
    else if (x > 1 && y > 1)
    {
        for (int i = 0; i < arrB.size(); i++) // arrB 내부의 요소 중 x로 나누어 떨어지는 요소가 있으면 useX를 false로 설정
        {
            if (arrB[i] % x == 0){
                useX = false;
                break; // 더 이상 확인할 필요 없으므로 반복 종료
            };
        }
        for (int i = 0; i < arrA.size(); i++) // arrA 내부의 요소 중 y로 나누어 떨어지는 요소가 있으면 useY를 false로 설정
        {
            if (arrA[i] % y == 0){
                useY = false;
                break; 
            }
        }
 
        if (useX == false && useY == false) return 0; // x와 y 모두 사용할 수 없으면 0 반환
        else if (useX && useY == false) return x; // x만 사용할 수 있으면 x 반환
        else if (useX == false && useY) return y; // y만 사용할 수 있으면 y 반환
        else return x > y ? x : y; // 둘 다 사용할 수 있으면 더 큰 값을 반환
    }
}

 

 

---