<문제>
두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.
<생각 흐름 상 풀이>
def solution(n, m):
for i in range(2, 1000000):
for j in range(2, 1000000):
if m%j == 0 and n%i == 0:
if i == j:
if i == n or j == m:
return [i, int(i*(m/i)*(n/i))]
else:
return [i,int((m/i)*(n/i))]
break
if n%m == 0:
return [m, n]
break
if m%n == 0:
return [n, m]
break
if (m%j != 0 and n%i !=0) and (n%m != 0) and (m%n != 0):
return [1, n*m]
elif (m%j == 0 and n%i !=0) and (n%m != 0) and (m%n != 0):
return [1, n*m]
elif (m%j!= 0 and n%i ==0) and (n%m != 0) and (m%n != 0):
return [1, n*m]
<최종 풀이>
def solution(n, m):
min_i = 0
max_i = 0
for i in range(min(n,m),0,-1):
if n%i == 0 and m%i == 0:
min_i = i
break
for i in range(max(n,m), (n*m)+1):
if i%n == 0 and i%m == 0:
max_i = i
break
return [min_i, max_i]
<다른 풀이>
방법 1.
def gcdlcm(a, b):
c, d = max(a, b), min(a, b)
t = 1
while t > 0:
t = c % d
c, d = d, t
answer = [c, int(a*b/c)]
return answer
방법 2.
def solution(n, m):
nlist = []
mlist = []
for i in range(1, n+1):
if n%i == 0:
nlist.append(i)
for i in range(1, m+1):
if m%i == 0:
mlist.append(i)
maxi=[]
for i in nlist:
if i in mlist:
maxi.append(i)
maximum = max(maxi)
minimum = int(maximum * (n/maximum) * (m/maximum))
answer = [maximum, minimum]
return answer
<개념>
방법 1: Euclidean algorithm 도입