LeetCode 풀기 - 1979. Find Greatest Common Divisor of Array

1979. Find Greatest Common Divisor of Array

https://leetcode.com/problems/find-greatest-common-divisor-of-array/

Find Greatest Common Divisor of Array - LeetCode

 

문제)

솔루션1)

• 최소, 최대 값을 구하고 최소값을 계속 감소시켜가면서 최소값, 최대값을 나눈 나머지가 0인 것을 찾는다.

class Solution:
    def findGCD(self, nums: List[int]) -> int:
        min_num = min(nums)
        max_num = max(nums)
        
        for n in range(min_num, 0, -1):
            if min_num % n == 0 and max_num % n == 0:
                return n
        return 0

솔루션2)

• 유클리드 호제법 사용

class Solution:
    def findGCD(self, nums: List[int]) -> int:
        min_num = min(nums)
        max_num = max(nums)
        
        while min_num:
            min_num, max_num = max_num % min_num, min_num        
        return max_num

솔루션3)

• 파이썬 최대공약수 구하는 라이브러리 사용 (GCD : Greatest Common Divisor)
• math.gcd()

class Solution:
    def findGCD(self, nums: List[int]) -> int:
        return math.gcd(max(nums), min(nums))