[Python/파이썬] 프로그래머스 Lv2 - 숫자 나누기 (유클리드호제법)

문제 설명

 

제한사항

 

입출력 예

 

---

Solution.py

첫 번째, 두 번째 조건을 보면 

철수가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고 영희가 가진 카드들에 적힌 모든 숫자들 중에 하나도 나눌수 없는 양의 정수 a => 철수가 가진 카드들의 최대 공약수

영희가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고 철수가 가진 카드들에 적힌 모든 숫자들 중에 하나도 나눌수 없는 양의 정수 a => 영희가 가진 카드들의 최대 공약수

로 해석할 수 있습니다.

 

1. 유클리드 호제법을 사용해 철수와 영희의 카드뭉치 최대공약수를 구하기
2. 구한 최대공약수로 두 조건들을 적용
3. 두 최대공약수 중 가장 큰 값을 반환

 

정답 코드

def solution(arrayA, arrayB):
    answer = 0
    
    # array의 첫 번째 값이 최대공약수로 가정 해 모든 요소와 비교하기 위해 아래처럼 초기화
    gcdA = arrayA[0]
    gcdB = arrayB[0]
    
    for n in arrayA[1:]:
        gcdA = gcd(n, gcdA)
        
    for n in arrayB[1:]:
        gcdB = gcd(n, gcdB)
        
    # 첫 번째 조건
    if notDiv(arrayA, gcdB):
        answer = max(answer, gcdB)
    
    # 두 번째 조건
    if notDiv(arrayB, gcdA):
        answer = max(answer, gcdA)
        
    return answer

# 최대공약수
def gcd(a, b):
    if a % b == 0:
        return b
    return gcd(b, a % b)

# 나누어떨어지는지
def notDiv(array, gcd):
    for n in array:
        if n % gcd == 0:
            return False
    return True