프로그래머스 / 수학, 정수론 / 숫자 카드 나누기

문제

---

 

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

프로그래머스

 

입출력

---

 

 

해설

---

 

문제를 정리하자면 다음 2가지 조건 중 하나를 만족시키는 가장 큰 정수를 구하는 문제이다.

 

1. A배열의 공약수 중 B배열과 서로소인 수

2. B배열의 공약수 중 A배열과 서로소인 수

 

문제를 잘 생각해보면 가장 큰 정수를 구하는 문제이지만 단순히 정수를 구하는 문제라고 생각해보자.

 

1이라는 숫자는 모든 숫자들을 나눌 수 있다.

그럼 정수를 구할 수 있으려면 일단 공약수를 알아내어야 할 것 같다.

 

고로 최대공약수를 구하여서 공약수를 빠르게 구할 수 있게 해준다.

1. A배열과 B배열의 최대공약수를 각각 구해준다.

 

그럼 최대공약수를 구해주었다면 그 수로 나머지 배열의 값을 각각 나누어본다.

만약 나누어 진다면 넘어가고 나누어 떨어지지 않는다면 정답인 것이다.

 

왜냐면 최대공약수로 나누어졌다는 사실은 그에 따른 공약수들도 다 나뉜다는 의미가 되기 때문이다.

그렇기 때문에 최대공약수로 나누어 떨어지는 것만 판단해주면 된다.

 

정답코드

---

'''
1. A 배열의 공약수 중 B 배열과 서로소인 수

2. B 배열의 공약수 중 A 배열과 서로소인 수

1. 각 최대공약수를 구해준다.
2. 해당 최대공약수를 기준으로 답을 구해준다.


'''
from math import gcd
def getGcd(array: list) -> int:
    ret = array[0]
    for i in range(1, len(array)):
        ret = gcd(ret, array[i])
    return ret

def isDivide(v: int, array: list) -> bool:
    for value in array:
        if value % v == 0:return True
    return False

def solution(arrayA, arrayB):
    answer = 0
    gcd_A = getGcd(arrayA)
    gcd_B = getGcd(arrayB)
    
    if not isDivide(gcd_A, arrayB):
        answer = gcd_A
    
    if not isDivide(gcd_B, arrayA):
        answer = max(answer, gcd_B)
        
    return answer

 

깃허브 : https://buly.kr/HSYUiKB

유튜브 : https://youtu.be/A-ZnATK9owU