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

 

Level. 2

 

문제

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

- 철수가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고 영희가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a
- 영희가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고, 철수가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 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에는 중복된 원소가 있을 수 있습니다.

 

 

풀이

#include <string>
#include <vector>
#include <iostream>
using namespace std;

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

int solution(vector<int> arrayA, vector<int> arrayB) {
    int answer = 0;
    
    int num1 = arrayA[0], num2 = arrayB[0];
    for(int i=0; i<arrayA.size(); i++){
        num1 = gcd(max(num1, arrayA[i]), min(num1, arrayA[i]));
    }
    
    for(int i=0; i<arrayB.size(); i++){
        num2 = gcd(max(num2, arrayB[i]), min(num2, arrayB[i]));
    }
    
    int answer1 = num2;
    for(int i=0; i<arrayA.size(); i++){
        if(arrayA[i]%num2 == 0) {
            answer1 = 0;
            break;
        }
    }
    
    int answer2 = num1;
    for(int i=0; i<arrayB.size(); i++){
        if(arrayB[i]%num1 == 0) {
            answer2 = 0;
            break;
        }
    }
    
    return max(answer1, answer2);
}

 

해결방법

1. arrayA와 arrayB의 요소들의 최대공약수(num1, num2)를각각 구해준다. 이 때 유클리드호재법을 사용하였다.
2. answer1 에는 arrayA의 최대공약수인 num1을,  answer2 에는 arrayB의 최대공약수인 num2을 저장한다. 
3. arrrayA의 요소들 중 하나라도 num2로 나누어진다면 answer1을 0으로 만든다. 
4. arrrayB의 요소들 중 하나라도 num1로 나누어진다면 answer2을 0으로 만든다. 
5. answer1, answer2의 max값을 리턴한다. 

 

 

---

다른 풀이

#include <bits/stdc++.h>
using namespace std;

int f(int a, int b){return a % b == 0 ? b : f(b, a % b);}
int f(vector<int> &a, vector<int> &b){
    int A = a[0];
    for (int x : a) A = f(max(A, x), min(A, x));
    for (int x : b)
    if (x % A == 0)
        return 0;
    return A;
}
int solution(vector<int> a, vector<int> b) {
    return max(f(a, b), f(b, a));
}

 

내 풀이에는 반복되는 부분이 많았는데, 위 풀이는 그러한 반복되는 부분을 모두 함수로 만들어주었다. 

---

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

프로그래머스