[day9] 코딩테스트 알고리즘 - 연습문제 (N개의 최소공배수) python (feat.gcd)

프로그래머스 N개의 최소공배수

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

나의 풀이

최대곱값 = 최대값을 찾아 +1 씩 곱해줌.

배열을 순회하며  모든 원소가 최대곱값 %  i == 0 인 경우를 찾는다. 그때의 최대곱값이 최소공배수.

def solution(arr):
  answer = 0
  n = 1
  while True:
    flag = True
    maxMulti = max(arr) * n
    for i in list(arr):
      if maxMulti % i != 0:
        flag = False
    if flag == False:
      n += 1
      continue
    else:
      answer = maxMulti
      break
  return answer

 

다른사람의 풀이

다른풀이를 보니 gcd 함수를 적용했다.

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


def nlcm(num):
    num.sort()
    max_num = num[-1]
    temp = 1
    for i in range(len(num)):
        temp = (num[i] * temp) / (gcd(num[i], temp))
    return temp

gcd의 함수의 방식을 살펴보면 

(1...n-1) n,의 두 수의 최소 공배수를 찾아준다.

총 4번만 for문을 돌리면 끝이다. gcd안에서도 재귀적으로 함수를 호출하긴 한다.