[연습문제] N개의 최소공배수 - Python / JavaScript

문제 링크 - https://school.programmers.co.kr/learn/courses/30/lessons/12953

프로그래머스

 

[문제 간단 요약]

1. 주어진 배열의 값의 최소공배수를 구하는 문제

[문제 해결 방안]

1. 유클리드 호제법을 활용하여 최소공배수 계산

 

[유클리드 호제법]

1. 큰 수 a / 작은 수 b / a를 b로 나눈 나머지 r이 있을 때, a와 b / b와 r의 최대 공약수는 같음

2.  나머지가 0이 될 때까지 연속해서 사용하여 나누는 값을 최대 공약수

최대 공배수 구하기

 

[최소 공약수]

1. 최소 공약수 =  큰 수 a * 작은 수 b / 최대 공약수

 

[문제 해결 코드 - python]

def GCD(a,b):
    while True:
        if a % b == 0:
            return b
        tmp = a % b
        a = b
        b = tmp

def solution(arr):
    answer = 0
    sort_arr = sorted(arr)
    a = sort_arr.pop()
    while sort_arr:
        b = sort_arr.pop()
        tmp = a * b
        a = tmp / GCD(a,b)
    return a

 

[문제 해결 코드 - javascript]

function GCD(a,b) {
    while (true) {
        if (a % b === 0) {
            return b
        }
        let tmp = a % b
        a = b
        b = tmp
    }
}

function solution(arr) {
    let a,b
    let arr_sort = arr.sort((a,b) => a-b)
    a = arr_sort.pop()
    while (arr_sort.length !== 0) {
        b = arr_sort.pop()
        let tmp = GCD(a,b)
        a = a * b / GCD(a,b)
        }
    return a;
}