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

[문제 출처]

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

1. 문제

설명

철수와 영희는 선생님으로부터 숫자가 하나씩 적힌 카드들을 절반씩 나눠서 가진 후, 다음 두 조건 중 하나를 만족하는 가장 큰 양의 정수 a의 값을 구하려고 합니다.

1. 철수가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고 영희가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a
2. 영희가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고, 철수가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a

예를 들어, 카드들에 10, 5, 20, 17이 적혀 있는 경우에 대해 생각해 봅시다. 만약, 철수가 [10, 17]이 적힌 카드를 갖고, 영희가 [5, 20]이 적힌 카드를 갖는다면 두 조건 중 하나를 만족하는 양의 정수 a는 존재하지 않습니다. 하지만, 철수가 [10, 20]이 적힌 카드를 갖고, 영희가 [5, 17]이 적힌 카드를 갖는다면, 철수가 가진 카드들의 숫자는 모두 10으로 나눌 수 있고, 영희가 가진 카드들의 숫자는 모두 10으로 나눌 수 없습니다. 따라서 철수와 영희는 각각 [10, 20]이 적힌 카드, [5, 17]이 적힌 카드로 나눠 가졌다면 조건에 해당하는 양의 정수 a는 10이 됩니다.

철수가 가진 카드에 적힌 숫자들을 나타내는 정수 배열 arrayA와 영희가 가진 카드에 적힌 숫자들을 나타내는 정수 배열 arrayB가 주어졌을 때, 주어진 조건을 만족하는 가장 큰 양의 정수 a를 return하도록 solution 함수를 완성해 주세요. 만약, 조건을 만족하는 a가 없다면, 0을 return 해 주세요.

 

제한사항

• 1 ≤ arrayA의 길이 = arrayB의 길이 ≤ 500,000
• 1 ≤ arrayA의 원소, arrayB의 원소 ≤ 100,000,000
• arrayA와 arrayB에는 중복된 원소가 있을 수 있습니다.

입출력 예

arrayA	arrayB	result
[10, 17]	[5, 20]	0
[10, 20]	[5, 17]	10
[14, 35, 119]	[18, 30, 102]	7

2. 설명

 먼저 '가진 카드들에 적힌 모든숫자를 나눌수 있고' 라는 조건을 만족시키기 위해서 arrayA, B모두 최대공약수를 구해주었습니다. 이때 유클리드 호제법을 사용해서 리턴해주었습니다. 각각의 최대공약수를 agcd, bgcd에 넣어줍니다.

 

다음으로는 '다른사람이 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 정수'의 조건을 만족시키키위해서 포문을 돌려주었습니다. 먼저 flag를 선언하여 각각 초기값 1을 설정해줍니다. 만약 arrayB의 원소가 agcd에 나누어 떨어진다면 조건을 만족하지 못하므로 flagA=0으로 바꿔줍니다. arrayA와 bgcd도 마찬가지로 해서 flag를 바꿔줍니다. 만약 둘다0이라면 모두 조건을 불만족함으로 break로 빠져나옵니다.

 

만약 flagA==1, flagB==1일경우 모두 만족하니까 agcd, bgcd중 큰것을 answer에 넣습니다.

만약 flagA만 1일경우, agcd를 넣습니다.

만약 flagB만 1일경우, bgcd를 넣습니다.

모두 0일경우 0을 넣습니다.

 

3. 코드

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

using namespace std;

int getGCD(int a, int b){
    
    int r,big=b,small=a;
    
    while(1){
        r=big%small;
        if(r==0)
            return small;
        big=small;
        small=r;
    }
}


int solution(vector<int> arrayA, vector<int> arrayB) {
    int answer = 0;
    int agcd=arrayA[0], bgcd=arrayB[0];
    int flagA=1, flagB=1;
    
    for(int i=0; i<arrayA.size(); i++){
        agcd=getGCD(agcd,arrayA[i]);
        bgcd=getGCD(bgcd,arrayB[i]);
    }
    
    for(int i=0; i<arrayA.size(); i++){
        if(arrayB[i]%agcd==0)
            flagA=0;
        if(arrayA[i]%bgcd==0)
            flagB=0;
        
        if(flagA==0 && flagB==0)
            break;
    }

    if(flagA==1 && flagB==1)
        answer=max(agcd,bgcd);
    else if(flagA==1)
        answer=agcd;
    else if(flagB==1)
        answer=bgcd;
    else
        answer=0;
    
    return answer;
}