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

프로그래머스의 레벨 2 문제 숫자 카드 나누기입니다.

문제 요구 조건

배열 A, B가 있을 때 A 원소들의 공약수이면서 B 원소들은 하나도 나눌 수 없는 수 중에서 가장 큰 수를 구하고, B 원소들의 공약수이면서 A 원소들은 하나도 나눌 수 없는 수 중에서 가장 큰 수를 구해서 더 큰 수를 리턴해야 합니다.

내 풀이 방법

1. 배열의 범위가 크고 원소 값의 범위도 크기 때문에 완전탐색으로 해결할 수 없는 문제라고 생각했습니다. 탐색 시간을 줄이기 위해서 각 배열에서 가장 작은 수의 약수만 구합니다.
2. 구한 약수들을 큰 순서대로 탐색하면서 조건에 맞는지 확인합니다.

 # 배열의 길이가 50만, 원소의 범위는 1~1억이다.
 # 이걸 일일이 확인하면 시간 내에 풀 수 없다.
 # 시간을 단축하는 방법으로, 나눌 수 있는 것은 약수니까 각 수들의 약수를 확인하자.
 # 그런데 최대공약수니까 가장 작은 수의 약수만 확인하면 되네!
 ​
 def maxDivisor(divisors, arrayA, arrayB):
     result = 0
     for divisor in divisors[::-1]:
         can = True
         for valueA, valueB in zip(arrayA, arrayB):
             if valueA % divisor != 0 or valueB % divisor == 0:
                 can = False
                 break
         if can:
             result = max(result, divisor)
             break
     return result
 ​
 def getDivisors(value):
     divisors = set([value])
     for i in range(1, int(value ** 0.5) + 1):
         if value % i == 0:
             divisors.add(i)
             divisors.add(value // i)
     return list(sorted(divisors))
 ​
 def solution(arrayA, arrayB):
 ​
     divisorsA = getDivisors(min(arrayA))
     divisorsB = getDivisors(min(arrayB))
     return max(maxDivisor(divisorsA, arrayA, arrayB), maxDivisor(divisorsB, arrayB, arrayA))

다른 사람의 풀이법

여러가지 종류가 있었지만 눈에 띈 방법은 아래와 같습니다.

1. 각 배열을 순회하면서 모든 원소들과의 최대공약수를 구하고, 조건에 맞는지 확인합니다.

오류가 있으면 언제든지 지적해 주세요. 생각을 공유하는 것도 좋아합니다!