[코테] 숫자 카드 나누기

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

프로그래머스

 

문제요약: 

두 개의 배열이 주어질 때 한 배열은 모두 나누어떨어지고 한 배열엔 하나도 나누어 떨어지지 않는 숫자 중 가장 큰 수a를 구하시오.

 

소요시간:

25분

 

난이도:

level2

 

제출횟수:

2회

 

코딩:

def solution(arrayA,arrayB):
    def gcd(a,b):
        while b!=0:
            r = a%b
            a = b
            b = r
        return a
    def find(A):
        if len(A)==1:
            return A[0]
        m = gcd(A[0],A[1])
        for a in range(2,len(A)):
            m = gcd(m,A[a])
            if m==1:
                break
        return m
    mA = find(arrayA)
    mB = find(arrayB)
    LmA = [[a,1] for a in range(2,mA//2+1) if not mA%a ]
    LmB = [[a,0] for a in range(2,mB//2+1) if not mB%a]
    L = LmA+LmB+[[mA,1],[mB,0]]
    L.sort(key= lambda x :x[0],reverse = True)
    
    Arr= [arrayA,arrayB]
    for n,arr in L:
        for i in Arr[arr]:
            if i%n:
                pass
            else:
                break
        else:
            return n
    return 0

먼저 최소공배수를 구하는 로직 gcd를 짜주고 각 배열을 순환하며 각 배열 전체의 최소 공배수를 구해줍니다. (이때 길이가 1이될 수 있으므로 예외처리를 해줘야함 이걸로 제출 날림) 그 후 그 최소공배수를 나열한뒤 만약 a배열에서 나온숫자라고 한다면 b배열에서 그 숫자를 하나씩 나눠보면서 전체가 다 나누어 떨어지지 않으면 탈출하여 그 숫자를 반환합니다. 준비되어있는 숫자를 전부 다 하면 for문이 종료되므로 0을 반환해 주었습니다.

 

다른사람 풀이:

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

사실 이번 문제는 문제에서 말해준 과정들을 구현을 열심히하면 시간복잡도와 상관없이 풀리는 문제였습니다. 하지만 구현과정을 다른사람들이 더 빠르고 가시적으로 보기쉽게 푼 풀이가 있어 리마인드 차 기록해봅니다.

먼저 math모듈에 구현이 되어있는 gcd가 있고, functools 에 reduce함수가 있는데 이는

def reduce(function, iterable, initializer=None):
    it = iter(iterable)
    if initializer is None:
        value = next(it)
    else:
        value = initializer
    for element in it:
        value = function(value, element)
    return value

이런식으로 선언되어있습니다. 초기값을 선언해주지 않으면 첫번째 인자값이 시작값이고, 선언해주면 초기값이 첫번째값이 됩니다.

그 이후 function을 기존값과 그다음값을 진행한 뒤 그값을 다시 value에 저장시켜줍니다. 위 함수를 통해 각 배열의 전체의 최대공약수를 구하는데 가난하게 서술할 수 있었고, 각 값을 나머지 배열에 나눠보는것 역시 all함수를 통해 다음과같이 깔끔하게 정리할 수 있었습니다.