[Programmers] Lv2. 숫자 카드 나누기 Python 문제 풀이

문제

https://school.programmers.co.kr/learn/courses/30/lessons/135807?language=python3

프로그래머스

 

어떻게 풀 것인가?

예시 : arrayA = [14, 35, 119], arrayB = [18, 30, 102]

 

1단계: "모든 수를 나눌 수 있는 a"는 결국 GCD다.

문제 조건: a가 배열의 모든 수를 나눠야 한다 → a는 모든 수의 공약수

 

공약수 중 가장 큰 것 = GCD이고, GCD의 약수들도 전부 공약수이므로 GCD만 확인하면 충분하다. GCD가 조건을 만족 못하면 그 약수들도 못 만족하기 때문이다.

 

사실 약수는 만족할 수 있다. 하지만 문제는 가장 큰 a를 구하는 것이므로, GCD부터 확인하면 된다.

• gcd_a = gcd(14, 35, 119) = 7
• gcd_b = gcd(18, 30, 102) = 6

 

2단계: 상대방 배열을 나눌 수 없는지 확인

 

조건 1 확인: gcd_a = 7이 arrayB의 어떤 수도 나누면 안 됨

• 18 % 7 = 4 → 나눠지지 않음
• 30 % 7 = 2 → 나눠지지 않음
• 102 % 7 = 4 → 나눠지지 않음
• candidate_a = 7

 

조건 2 확인: gcd_b = 6이 arrayA의 어떤 수도 나누면 안 됨

• 14 % 6 = 2 → 나눠지지 않음
• 35 % 6 = 5 → 나눠지지 않음
• 119 % 6 = 5 → 나눠지지 않음
• candidate_b = 6

 

3단계: 둘 중 큰 값 반환

 

max(7, 6) = 7 → 정답

 

코드

import math

def solution(arrayA, arrayB):
    # arrayA의 GCD: arrayA 모든 수를 나눌 수 있는 가장 큰 수
    gcd_a = arrayA[0]
    for i in arrayA:
        gcd_a = math.gcd(gcd_a, i)

    # arrayB의 GCD: arrayB 모든 수를 나눌 수 있는 가장 큰 수
    gcd_b = arrayB[0]
    for i in arrayB:
        gcd_b = math.gcd(gcd_b, i)

    # gcd_a가 arrayB의 어떤 수도 나누지 못하면 후보
    candidate_a = gcd_a
    for i in arrayB:
        if i % gcd_a == 0:
            candidate_a = 0
            break

    # gcd_b가 arrayA의 어떤 수도 나누지 못하면 후보
    candidate_b = gcd_b
    for i in arrayA:
        if i % gcd_b == 0:
            candidate_b = 0
            break

    return max(candidate_a, candidate_b)