문제 135807. 숫자 카드 나누기

문제 링크

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

프로그래머스

 

 

난이도 : Lv.2

 

문제 요약 설명

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

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

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

입력

• 철수가 가진 카드에 적힌 숫자들을 나타내는 정수 배열 arrayA
• 영희가 가진 카드에 적힌 숫자들을 나타내는 정수 배열 arrayB

입력 제한

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

입력 예제

// input
[10, 17]	// arrayA
[5, 20]		// arrayB

// ans
0

 

풀이 방식

이 문제를 보았을 때 가장 먼저 떠오르는 개념이 하나 있는데, 그것은 바로 최대 공약수이다. 왜냐하면 '가진 카드들에 적힌 모든 숫자를 나눌 수 있고... ' 라는 것 자체가 최대 공약수를 의미하기 때문이다. 따라서, 이 문제는 최대 공약수를 구하고 최대 공약수의 값이 반대편 카드들에 적힌 숫자들이 나누어지는 지 확인하면 된다. 가장 큰 양의 정수를 구하는 것이 목적이기 때문에 철수가 가진 카드들의 최대공약수가 영희의 카드 숫자들로부터 나누어지는 지 확인하고, 그 반대 또한 확인해서 둘 중 큰 값이 정답이 된다.

 

최대 공약수가 아닌 다른 약수가 정답이 될 가능성은 없을까?

이 문제를 풀다보면 위와 같은 의문점이 들었다. 왜냐하면 모종의 이유로 최대 공약수는 나눠지고 다른 약수로는 나눠지지 않는 경우가 한 번도 없을거라고 확신이 들지 않았기 때문이다. 하지만 조금 생각해보니 그런 경우는 절대로 발생할 수 없을 것이라는 걸 알아챘다.

최대공약수를 X, 다른 약수를 Y라고 가정해보자. 위에서 말했던 것처럼 해당 경우가 절대로 발생할 수 없는 이유는 반드시 Y*N = X(단, N은 자연수)라는 공식이 성립하기 때문이다. 즉, Y로 나눠지지 않았다면 Y*N 또한 항상 나눠질 수 없다. 

정답 코드 

#include <string>
#include <vector>
#include <bits/stdc++.h>

using namespace std;

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

int gcd_n(vector<int>& arr) {
    int result = arr[0];
    for(int i = 1; i < arr.size(); i++){
        result = gcd(result, arr[i]);
    }
    return result;
}

int solution(vector<int> arrayA, vector<int> arrayB) {
    int answer = 0;
    
    int gcdA = gcd_n(arrayA);       // arrayA의 최대 공약수
    int gcdB = gcd_n(arrayB);       // arrayB의 최대 공약수
    
    if(gcdA != 1){
        bool find = true;
        for(int elem : arrayB){
            if(elem % gcdA == 0){
                find = false;
                break;
            } 
        }
        
        if(find) answer = gcdA;
    }
    
    if(gcdB != 1){
        bool find = true;
        for(int elem : arrayA){
            if(elem % gcdB == 0){
                find = false;
                break;
            } 
        }
        
        if(find) answer = max(answer, gcdB);
    }
    
    return answer;
}