[프로그래머스] 숫자 카드 나누기

사용 언어: Python3

문제

숫자 카드 나누기

풀이

나의 풀이

def solution(arrayA, arrayB):
    # 중복 원소가 있으면 0리턴
    if len(set(arrayA)) + len(set(arrayB)) != len(set(arrayA + arrayB)):
        return 0
    
    # 약수 구하기
    def getPrimes(N):
        lst = []
        for i in range(1, N+1):
            if N % i == 0:
                lst.append(i)
        return lst
    
    # 유클리드 호제법으로 최대공약수 구하기
    def GCD(a, b):
        while b != 0:
            r = a % b
            a, b = b, r
        return a
    
    def process(arr1, arr2): # arr1의 공약수 중에서 arr2를 하나도 나눌 수 없는 것
        if len(arr1) == 1:
            gcd = arr1[0]
        else: # 여러 수(arr1)의 최대공약수 구하기
            gcd = GCD(arr1[0], arr1[1])
            for i in range(2, len(arr1)):
                gcd = GCD(gcd, arr1[i])

        # 최대공약수의 약수가 공약수
        primes = getPrimes(gcd)

        # arr1의 공약수 중 arr2를 하나도 나눌 수 없는 것 append
        for prime in primes:
            if all(b % prime != 0 for b in arr2):
                ans.append(prime)
            
    ans = []
    process(arrayA, arrayB) # 조건 1
    process(arrayB, arrayA) # 조건 2
    
    if len(ans) == 0:
        return 0
    
    return max(ans)

• 테스트 케이스: 통과
• 제출 결과: 통과
• 최대공약수와 공약수 이용해서 풀었다.
  • arrayA의 최대공약수 gcd를 구한다.
  • 공약수는 최대공약수 gcd의 약수이다.
  • arrayA의 공약수 리스트를 순회하며 arrayB를 모두 나눌 수 없는 원소만 ans 리스트에 추가한다.
  • 반대의 경우도 실행해 ans 리스트에 추가한다.
  • ans 리스트 중 max 값을 반환한다.

나의 풀이 (개선된 풀이)

def solution(arrayA, arrayB):
    # ✅ 중복 원소가 있으면 0 리턴
    if len(set(arrayA)) + len(set(arrayB)) != len(set(arrayA + arrayB)):
        return 0
    
    # ✅ 유클리드 호제법으로 최대공약수 구하기
    def GCD(a, b):
        while b != 0:
            r = a % b
            a, b = b, r
        return a
    
    # arr1의 최대공약수가 arr2의 모든 원소를 나눌 수 없다면 ans에 append
    def process(arr1, arr2):
        if len(arr1) == 1:
            gcd = arr1[0]
        else: # ✅ 여러 수(arr1)의 최대공약수 구하기
            gcd = GCD(arr1[0], arr1[1])
            for i in range(2, len(arr1)):
                gcd = GCD(gcd, arr1[i]) # gcd 갱신
        
        # ✅ gcd가 arr2 원소들 모두를 나눌 수 없다면 a가 될 수 있으니 ans에 append 
        if all(b % gcd != 0 for b in arr2):
            ans.append(gcd)
            
    ans = [] # ✅ 조건 1을 만족하거나 조건 2를 만족하는 a 모임
    process(arrayA, arrayB) # 조건 1
    process(arrayB, arrayA) # 조건 2
    
    if len(ans) == 0:
        return 0
    
    return max(ans)

• 테스트 케이스: 통과
• 제출 결과: 통과
• 굳이 공약수를 구할 필용가 없었다.
  • 최대 공약수만 구하면 된다! 🌟

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기