문제

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

풀이

아이디어

• 제한 사항 마지막에서 '중복'이 있을 수 있다고 했으니 자바스크립트의 Set을 사용하여 중복을 제거해야겠다.
• 최대공약수를 구하는 문제이다.
  • 문제를 다시 해석하면 영희 카드의 최대공약수이지만 철수 카드 중 아무것도 나눌 수 없는 수 X와,
  • 철수 카드의 최대공약수이지만 영희 카드 중 아무것도 나눌 수 없는 수 Y 중에서
  • 최댓값을 구하되, X와 Y가 둘 다 존재하지 않으면 0을 리턴해라.
• 최대공약수를 구하기 위해서는 '유클리드 호제법'을 사용해야겠다 + Array.prototype.reduce 함수를 사용하면 좋겠다.

틀렸던 이유

• arrayA에서의 최대공약수는 arrayA에서 중복을 제거하고 오름차순으로 정렬했을 때 맨 앞 두 개의 최대공약수와 같다는 멍청한 생각을 하고 코드를 짜서 틀렸다. (반례: [8, 16, 20])
• (파이썬으로 다시 풀 때) arrayA에서 중복을 제거한 때랑 arrayB에서 중복을 제거한 때랑 당연히 원소 개수는 둘이 다를 수 있는데, gcd_a와 gcd_b를 구하는 과정에서 한 반복문으로 돌려서 런타임 에러가 계속 났었다.

통과한 코드

// 최대공약수 구하는 함수
function gcd(num1, num2) {
    const big = Math.max(num1, num2);
    const small = Math.min(num1, num2);
    
    if(small === 0) return big;
    return gcd(small, big % small);
}

// 배열의 중복을 없애서 반환하는 함수
function getUnique(arr) {
    const set = new Set(arr);
    return [...set];
}

function solution(arrayA, arrayB) {
    var answer = 0;
    
    // 우선 오름차순 정렬
    arrayA.sort((a, b) => a - b);
    arrayB.sort((a, b) => a - b);
    
    // 중복이 제거된 원소들의 배열
    let uniqueA = getUnique(arrayA);
    let uniqueB = getUnique(arrayB);
    
    // 각 배열에서 최대공약수 뽑아내기
    let gcdA = uniqueA.reduce((cur, acc) => {
        return gcd(cur, acc);
    }, 0);
    let gcdB = uniqueB.reduce((cur, acc) => {
        return gcd(cur, acc);
    }, 0);
    
    let defeatA = arrayA.some(num => num % gcdB === 0);
    let defeatB = arrayB.some(num => num % gcdA === 0);
    
    if(!defeatA) answer = gcdB;
    if(!defeatB) answer = Math.max(answer, gcdA);
    
    return answer;
}

파이썬 코드

import math
def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    
    return a

def solution(arrayA, arrayB):
    newA, newB = list(set(arrayA)), list(set(arrayB))
    newA.sort()
    newB.sort()
    #철수, 영희의 최대공약수
    gcd_a, gcd_b = newA[0], newB[0]
    for i in range(1, len(newA)):
        gcd_a = math.gcd(gcd_a, newA[i])
    for i in range(1, len(newB)):
        gcd_b = math.gcd(gcd_b, newB[i])
    
    candidates = []
    #철수의 최대공약수가 영희를 나눌 수 있는지?
    if not any(b % gcd_a == 0 for b in newB):
        candidates.append(gcd_a)
    
    #영희의 최대공약수가 철수를 나눌 수 있는지?
    if not any(a % gcd_b == 0 for a in newA):
        candidates.append(gcd_b)
    
    return max(candidates, default=0)