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

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

코딩테스트 연습 - N개의 최소공배수

 

실제로 n 개의 최소공배수를 풀 때 사용하는 알고리즘을 이용했다. 주어지는 숫자가 100이하의 숫자이므로 2부터 증가시키며 100보다 작은 동안 나누어지는 수를 계속 나누어준후 재수들의 리스트에 삽입하여 저장하였고 나누어진 수들을 전부곱하여 리턴하였다.

다른 사람의 풀이를 봤는데 파이썬에 최대공약수를 구해주는 내부 모듈이 존재했다. 최소공배수를 구하는 최대공약수를 이용한 공식있다는 것 또한 알게되었다.

 

 

풀이코드

def solution(arr):
  arr.sort()
  answer = 1
  div = []
  num = 2; flag = False
  while num<=100:
    for i in range(len(arr)):
      if arr[i]%num == 0 :
        arr[i] /=num
        flag = True
    if flag == True: # 한번이라도 나눴다면 추가
      flag = False
      div.append(num)
      num = 2
    else:
      num+=1
  for i in arr:
    answer*=i
  for i in div:
    answer*=i
  return int(answer)

다른 사람 풀이

import math
 
def nlcm(num):      
    answer = num[0]
    for n in num:
        answer = n * answer / math.gcd(n, answer)
  
    return answer