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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/135807

프로그래머스

 

설계

- 각 배열의 모든 숫자를 나눌 수 있는 가장 큰 수 = 최대 공약수

- 각 배열의 최대 공약수를 구한다 

- 각 배열의 최대 공약수가 다른 배열을 나눌 수 없는지 검사

- 조건을 만족하는 최대 공약수 중 더 큰 값이 정답!

# 2중 for문으로 구현했으나 시간초과로 통과하지 못했다.

def cal(arrayA, arrayB):
    maxV = 0
    for i in range(len(arrayA)):
        maxV = max(maxV, arrayA[i], arrayB[i])
    arrayA.sort(reverse=True)
    arrayB.sort(reverse=True)

    for i in range(maxV, 1, -1):
        cntA, cntB = 0, 0
        for j in range(len(arrayA)):
            if arrayA[j] % i == 0:
                cntA += 1
            else:
                break
            if arrayB[j] % i > 0:
                cntB += 1
            else:
                break
        if cntA == len(arrayA) and cntB == len(arrayB):
            return i
    return 0

# 최대공약수를 구하는 math 라이브러리안에 gcd를 사용

from math import gcd

def cal_gcd(arr):       # 최대공약수 구하기
    g = arr[0]
    for i in range(1, len(arr)):
        g = gcd(g, arr[i])      # 각 요소들의 최대공약수를 갱신하며 비교
    return g

def solution(arrayA, arrayB):
    N = len(arrayA)
    gcdA, gcdB = cal_gcd(arrayA), cal_gcd(arrayB)   # A와 B 배열의 최대공약수 구하기

    answer = 0
    cnt1, cnt2 = 0, 0
    for i in range(N):      # 1번 조건 확인
        if arrayB[i] % gcdA != 0:   # B를 나눌 수 있는지 확인
            cnt1 += 1
    if cnt1 == N:        # 모든 수를 나눌 수 없다면
        answer = max(answer, gcdA)      # 조건 만족!


    for i in range(N):      # 2번 조건 확인
        if arrayA[i] % gcdB != 0:  # A를 나눌 수 있는지 확인
            cnt2 += 1
    if cnt2 == N:  # 모든 수를 나눌 수 없다면
        answer = max(answer, gcdB)  # 조건 만족!

    return answer