[Programmers] 숫자 카드 나누기 바로가기
철수와 영희는 선생님으로부터 숫자가 하나씩 적힌 카드들을 절반씩 나눠서 가진 후, 다음 두 조건 중 하나를 만족하는 가장 큰 양의 정수 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 해 주세요.
arrayA
의 길이 = arrayB
의 길이 ≤ 500,000arrayA
의 원소, arrayB
의 원소 ≤ 100,000,000arrayA
와 arrayB
에는 중복된 원소가 있을 수 있습니다.arrayA | arrayB | result |
---|---|---|
[10, 17] | [5, 20] | 0 |
[10, 20] | [5, 17] | 10 |
[14, 35, 119] | [18, 30, 102] | 7 |
입출력 예 #1
입출력 예 #2
입출력 예 #3
arrayA
배열의 모든 원소의 공약수 중, arrayB
배열의 모든 원소를 나누었을 때 나누어지지 않는 가장 큰 양의 정수를 구하는 것이다.arrayA : [10, 20], arrayB : [5, 17]
arrayA
배열의 모든 원소의 공약수를 구하기 위해 arrayA
배열의 최대 공약수를 구한 후 최대 공약수의 약수들을 모두 구하였다.arrayA
배열의 최대 공약수 → 10
10
의 약수 → 1, 2, 5, 10
arrayA
배열 원소의 약수가 arrayB
배열의 모든 원소를 나누었을 때 나누어지지 않는지 확인한다.1
: 5
는 1
로 나누어지고, 17
또한 1
로 나누어진다. → X
2
: 5
는 2
로 나누어지지 않고, 17
또한 2
로 나누어지 않는다. → O
5
: 5
는 5
로 나누어지지만, 17
은 5
로 나누어지지 않는다. → X
10
: 5
는 10
로 나누지지 않고, 17
또한 10
로 나누어지지 않는다. → O
2
, 10
) 중 가장 큰 값인 10
을 반환한다.arrayA
→ arrayB
에 대한 경우를 구하고, arrayB
→ arrayA
에 대한 경우도 고려해야 한다.def func(arrayA, arrayB):
# 최대 공약수
GCD = reduce(gcd, arrayA)
# 공약수 후보
divisorCandidate = [i for i in range(GCD, 1, -1) if GCD % i == 0]
# 나누기 불가능 조건
for divisor in divisorCandidate:
if all(b % divisor for b in arrayB):
return divisor
return 0
gcd
와 arrayA
배열을 reduce
의 인자로 할당하여 arrayA
배열의 모든 원소의 최대 공약수(GCD
)를 구한다.GCD
)의 모든 공약수(divisorCandidate
)를 구한다.divisorCandidate
) 중 arrayB
배열의 모든 원소를 나누었을 때 나누어 떨어지지 않는 약수(divisor
)를 반환한다.from math import gcd
from functools import reduce
def solution(arrayA, arrayB):
def func(arrayA, arrayB):
# 최대 공약수
GCD = reduce(gcd, arrayA)
# 공약수 후보
divisorCandidate = [i for i in range(GCD, 1, -1) if GCD % i == 0]
# 나누기 불가능 조건
for divisor in divisorCandidate:
if all(b % divisor for b in arrayB):
return divisor
return 0
return max(func(arrayA, arrayB), func(arrayB, arrayA))