99클럽 코테 스터디 2일차 TIL + 유클리드 호제법

[오늘의 학습 키워드]
- 프로그래머스에서 "숫자 카드 나누기" 문제를 풀었다.
- 문제를 읽고 최대공약수와 유클리드 호제법이 떠올랐다. 마침 최근에 유클리드 호제법을 공부했던 터였다.

[나의 코드]

def gcd(a, b):
    if a % b == 0:
        return b
    return gcd(b, a % b)

def check_divided(array, gcd):
    for n in array:
        if n % gcd == 0:
            return False
    return True

def solution(arrayA, arrayB):
    answer = 0
    gcdA = arrayA[0]
    gcdB = arrayB[0]
    
    for n in arrayA[1:]:
        gcdA = gcd(n, gcdA)
        
    for n in arrayB[1:]:
        gcdB = gcd(n, gcdB)
    
    if check_divided(arrayA, gcdB):
        answer = max(answer, gcdB)
    
    if check_divided(arrayB, gcdA):
        answer = max(answer, gcdA)
    
    return answer

문제를 보고 떠오른 생각의 순서는 이렇다.
1. 각 배열의 최대공약수를 구한다. → 여기서 유클리드 호제 알고리즘을 씀
2. 조건을 확인한다.
3. 조건에 맞는다면 더 큰 숫자를 반환하고, 없다면 0을 반환한다.

막혔던 부분은 세 개 이상의 숫자에서 최대공약수를 어떻게 구하느냐였는데, 다른 분들의 풀이를 보니 별거 아니었다..ㅎㅎ
그리고 나보다 코드를 깔끔하게 쓰신 분의 코드대로 바꿔 작성했다. 역시 코드는 예쁘게 작성해야 한다.

[오늘의 회고]
- 생각보다 어떻게 풀어야 할지 답을 내놓는 것은 오래 걸리지 않았다. 이 문제를 풀기 위해서는 유클리드 호제법을 미리 알고 있는 것이 필요하고 (복습도 하자), 중복된 부분을 제거하고 깔끔하게 정리도 해주는 것도 중요했다. 끝!