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

 

이번 문제는 레벨 1에서 풀었던 [프로그래머스] 최대공약수와 최소공배수을 적용해서 풀었습니다.

제가 올린 [프로그래머스] 최대공약수와 최소공배수를 참고하시면 좋을 것 같아요.👏

https://development-piece.tistory.com/37

[프로그래머스] 최대공약수와 최소공배수

---

해결방안을 얘기하기 전 어떻게 풀었는지에 대해 설명을 하자면

 

제가 최소공배수를 구할 수 있는 방법이

유클리드 호제법을 써서 두 수의 최소공배수를 구하는 방법밖에 몰라서

이 방법을 적용하는게 최선의 방법이라고 생각했습니다.

 

 

 

유클리드 호제법에 대해 간단하게 설명하자면

 

[유클리드 호제법]

두 수 a, b가 있을 때 (a > b)

a % b === 0이면 b가 최대공약수입니다.

a % b !== 0이면 b에 +1씩 해주어 a % b === 0 나올 때까지 반복합니다.

(참고로 알면 좋을 것 같아서 씁니다.)
두 수 (a, b)
a x b = 최대공약수 * 최소공배수

 

 

 

유클리드 호제법을 활용해서 어떻게 구했나면

[2,6,8,14]가 있으면

2, 6의 최대공약수는 6

6, 8의 최대공약수는 24

24, 14의 최대공약수는 168

 

이런 식으로 구했습니다.

 

해결방안

function solution(arr) {    
    let a = arr[0];
    let lcm;
    for(let i=1; i<arr.length; i++){
        lcm = Math.max(a, arr[i]);
        while(true){
            if((lcm % a === 0) && (lcm % arr[i] === 0)){
                a = lcm;
                break;
            }
            lcm++;
        }
    }    
    return lcm;
}

 

let a = arr[0];

a는 두 수(a, b)가 있으면 a를 나타내는 주는 변수입니다.

a는 두 수의 최대공배수를 구한 값을 넣는 곳인데

초기값을 설정해 주었을 때 최대공배수가 없어서 arr[0]을 넣어주었습니다.

 

[2,6,8,14]가 있으면 a의 초기값은 2입니다.

 

 

 

let lcm;

lcm은 최대공배수를 담아주는 변수입니다.

 

 

 

for(let i=1; i<arr.length; i++)

여기서 반복문을 쓰는 이유는

 

arr = [2,6,8,14]

2, 6의 최대공약수는 6

6, 8의 최대공약수는 24

24, 14의 최대공약수는 168

 

여기서 파란색 숫자가 arr배열의 원소입니다.

순서대로 사용해서 쓸 생각이라 for문을 써주었고

 

변수 a의 초기값 설정으로 arr[0]을 사용했습니다.

반복문에서는 arr[1]부터 사용할 거라서 i=1로 초기값을 설정했습니다.

 

 

 

for문 안에 코드는 밑에 최소공배수를 구하는 코드를 거의 그대로 넣어 주었습니다.

function solution(n, m) {
    // 최소공배수
    let lcm = Math.max(n, m);
    while(true){
        if((lcm % n === 0) && (lcm % m === 0)){
            break;
        }
        lcm++;
    }    
    return lcm;
}

 

---

여기까지 프로그래머스 N개의 최소공배수 해결방안에 대해 설명해보았습니다.