[프로그래머스] 숫자 카드 나누기 C++ 풀이 및 해설

풀이 방법

1. 철수 카드들의 최대 공약수를 구한다.
2. 영희 카드들의 최대 공약수를 구한다.
3. 철수의 최대 공약수로 영희의 카드들을 하나도 나눌 수 없는지 확인한다.
   1. 확인 결과를 bool A에 저장
4. 영희의 최대 공약수로 철수 카드들을 하나도 나눌 수 없는지 확인한다.
   1. 확인 결과를 bool B에 저장
5. A가 true 라면, 즉. 철수의 최대 공약수로 영희의 카드들을 나눌 수 없다면
   1. answer의 값을 철수의 최대 공약수로 갱신
6. B가 true 라면, 즉. 영희의 최대 공약수로 철수의 카드들을 나눌 수 없다면
   1. 영희의 최대 공약수가 answer의 값보다 크다면 answer를 영희의 최대 공약수로 갱신

 

풀이 코드

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

using namespace std;

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

int solution(vector<int> arrayA, vector<int> arrayB) {
    int answer = 0;
    
    
    // 길이는 최소 1이라 0번째 값을 최대 공약수로 설정
    int chulSu = arrayA[0];
    int youngHee = arrayB[0];
    
    // A와 B의 길이는 동일하다.
    // A와 B의 최대 공약수 구하기.
    for(int i=1; i<arrayA.size(); i++) {
        chulSu = gcd(chulSu, arrayA[i]);
        youngHee = gcd(youngHee, arrayB[i]);
    }
    
    // A(chulSu): chulSu의 최대 공약수로 youngHee 카드를 모두 나눌 수 있는가?
    // B는 영희의 최대 공약수로 철수 카드들을 모두 나눌 수 있는가?
    bool A = true; // 초기값 : 가능(true)
    bool B = true;
    for(int i=0; i<arrayA.size(); i++) {
        if (A&&arrayB[i]%chulSu==0) { // A가 현재 가능 상태이고 chulSu(A)것으로 영희의 i번째 나눠진다면
            A=false; // A(chulSu의 최대 공약수)는 정답이 될 수 없으므로 false 처리.
        }
        if (B&&arrayA[i]%youngHee==0) {
            B=false;
        }
    }
    
    if(A) { // A가 참이라면 chulSu의 최대 공약수로 영희 카드들을 모두 나눌 수 없는것
        answer = chulSu;
    }
    
    if(B) { // B가 참이라면 youngHee의 최대 공약수로 철수 카드들을 모두 나눌 수 없는것
        answer = max(answer, youngHee);
    }
    
    return answer;
}