코딩 테스트 일기 - 9일 차

숫자 카드 나누기

문제 링크 : 숫자 카드 나누기

문제 설명

철수와 영희는 선생님으로부터 숫자가 하나씩 적힌 카드들을 절반씩 나눠서 가진 후, 다음 두 조건 중 하나를 만족하는 가장 큰 양의 정수 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에는 중복된 원소가 있을 수 있습니다.

입출력 예

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

풀이 방법

• 철수나, 영희가 가진 카드들에 모든 숫자를 나눌 수 있는 숫자는 모든 숫자들에 대한 공약수인데, 가장 큰 양의 정수 값을 찾기 때문에 먼저 최대 공약수를 찾고자 했다. 또한 다른 반대편 숫자들은 못 나눠야 하는데, 최대 공약수를 나눴을 때 나눌 수 있으면 당연히 다른 공약수들도 나눌 수 있기 때문에 최대 공약수만 확인하면 될 것이다.
  -> 최대 공약수를 구하는 알고리즘은 O(logN)의 시간복잡도를 가지고, arrayA만큼 반복해야하기 때문에 O(N*logN)의 시간복잡도가 걸릴 것으로 추정된다.
• 배열의 최대 공약수를 구하고, 반대편 숫자들을 나눠보면서 나눠진다면 해당 배열에는 a라는 수가 존재하지 않기 때문에 이를 확인하고, 둘 다 있다면 더 큰 수를 값으로 반환했다.
  -> 반대편 숫자들을 모든 확인하는 데에는 O(N)만큼의 시간복잡도가 걸릴 것으로 추정된다.
  -> 결론적으로 이 알고리즘은 O(N*logN)의 시간복잡도가 걸리는데, N은 500,000이 최대값이기 때문에 알맞은 알고리즘으로 보인다.

구현

#include <string>
#include <vector>

using namespace std;

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

int solution(vector<int> arrayA, vector<int> arrayB) {
    int answer = 0;
    
    int gcd_A = arrayA[0];
    int gcd_B = arrayB[0];
    for(int i = 1; i < arrayA.size(); i++){
        gcd_A = gcd(arrayA[i], gcd_A);
        gcd_B = gcd(arrayB[i], gcd_B);
    }
    
    for(int i = 0; i < arrayA.size(); i++){
        if(arrayA[i] % gcd_B == 0)
            gcd_B = 1;
        
        if(arrayB[i] % gcd_A == 0)
            gcd_A = 1;
        
        if(gcd_A == 1 && gcd_B == 1)
            break;
    }
    
    if(gcd_A != gcd_B) 
        answer = max(gcd_A, gcd_B);
    
    return answer;
}