[알고리즘] 프로그래머스 Lv2 숫자 카드 나누기

문제

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

풀이과정

1. 각 배열의 최대공약수를 구한다
2. 최대공약수 약수의 배열을 만든다
3. 약수의 배열 원소 중 상대 배열을 나눌 수 없는 값을 answer로 업데이트 한다
4. 이때, 기존 answer과 비교해서 큰 값만 남긴다

이렇게 어렵고 복잡하게 풀고 나서 다른 사람의 풀이를 보니, 자신의 배열의 약수이고 상대 배열을 나눌 수 없는 수 중 가장 큰 수가 답이 되므로 최대공약수만 비교하면 되는 것이었다..!
(예를 들어 42는 50으로 나누어 떨어지지 않는다. 왜냐면, 50이 더 큰 수니까.)

코드

# 프로그래머스 Lv2 숫자 카드 나누기
import math

# arrayA의 약수 중 arrayB를 나눌 수 없거나
# arrayB의 약수 중 arrayA를 나눌 수 없는 숫자 a 중 가장 큰 값, 없으면 0
def solution(arrayA, arrayB):
    answer = 0
    gcd_A = arrayA[0]
    gcd_B = arrayB[0]
    i = 1
    while i < len(arrayA):
        gcd_A = math.gcd(gcd_A, arrayA[i])
        gcd_B = math.gcd(gcd_B, arrayB[i])
        i += 1

    if gcd_A == 1 and gcd_B == 1:
        return 0

    div_A = []
    div_B = []
    if gcd_A != 1:
        a = 2
        while a < (gcd_A)**(1/2):
            if gcd_A % a == 0:
                div_A.extend([a, gcd_A//a])
            a += 1
        div_A.append(gcd_A)
    if gcd_B != 1:
        b = 2
        while b < (gcd_B)**(1/2):
            if gcd_B % b == 0:
                div_B.extend([b, gcd_B//b])
            b += 1
        div_B.append(gcd_B)

    # print(div_A, div_B)
    while div_A:
        tmp = div_A.pop()
        if all([i % tmp != 0 for i in arrayB]):
            answer = max(answer, tmp)

    while div_B:
        tmp = div_B.pop()
        if all([i % tmp != 0 for i in arrayA]):
            answer = max(answer, tmp)

    return answer

arrayA = [10, 17]
arrayB = [5, 20]
arrayA = [10, 20]
arrayB = [5, 17]
# arrayA = [14, 35, 119]
# arrayB = [18, 30, 102]
print(solution(arrayA, arrayB))

다른 사람의 풀이

from functools import reduce
from math import gcd


def solution(nums1, nums2):
    gcd1, gcd2 = reduce(gcd, nums1), reduce(gcd, nums2)
    answer = []
    if all(each % gcd2 for each in nums1):
        answer.append(gcd2)
    if all(each % gcd1 for each in nums2):
        answer.append(gcd1)
    return max(answer) if answer else 0

오 파이써닉...
reduce 함수라는 것을 처음 접했다.
강력하다.

functools의 reduce

https://docs.python.org/3/library/functools.html

functools.reduce(function, iterable[, initializer])

Apply function of two arguments cumulatively to the items of iterable, from left to right, so as to reduce the iterable to a single value. For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates ((((1+2)+3)+4)+5). The left argument, x, is the accumulated value and the right argument, y, is the update value from the iterable. If the optional initializer is present, it is placed before the items of the iterable in the calculation, and serves as a default when the iterable is empty. If initializer is not given and iterable contains only one item, the first item is returned.

javascript 배열의 메서드 reduce와 닮아있는 듯 하다.

functools.reduce(함수, 반복 가능한 배열)을 하면 함수에 인자 두 개씩 넣어서 계산하고 반복 가능한 배열에서 하나 씩 빼와서 앞선 함수의 결과와 다시 함수에 넣어서 계산하고... 반복반복 => reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates ((((1+2)+3)+4)+5) 이렇게