프로그래머스: 최대공약수 & 최소공배수(Math.max)
in Algorithm
프로그래머스 ‘최대공약수와 최소공배수’ 문제.
나의 해결방안
my solution
function solution(n, m) {
var answer = [];
let gcd = 0;
let lcm = 0;
//최대공약수
for(let i=1; i<=Math.max(n,m); i++){
if(n % i === 0 && m % i ===0){
gcd = i;
}
}
//최소공배수 (두수의곱 = 최대공약수 * 최대공배수)
lcm = (n * m) / gcd;
answer=[gcd,lcm];
return answer;
}
우선 1로 시작하고 n으로 나누어 떨어지는 for문을 돌린다(=약수구하기)
여기서 길이를 얼만큼으로 정할지 생각하고 나는 최대값으로 생각하고 for(let i=1; i<=Math.max(n,m); i++){ 에
Math.max(n,m) 로 돌렸는데 min으로 해도 상관없나보다…
둘다 상관없이 같은 결과가 나옴…!
여튼 n이나 m중에 가장 큰 수를 골라서 그만큼 for문을 돌린다.
(for문을 0으로 시작하지 않는 이유는 나누어버리면 무조건 0이기 때문임)
1부터시작해서 n,m중 가장 큰 수만큼 for문을 돌린다
근데 최대공약수도 어쨌거나 약수 중에 가장 큰 수이기 때문에 결국에는 약수를 구해야하는데
약수를 구해야하는데, 약수는 i로 나누어지는 숫자들이 약수가 된다.
for (let i = 0; i <= n; i++) {
if( n % i === 0) { answer += i}
}
이렇게 나머지가 0이면 n의 약수가 된다.
이중에서 가장 큰 수를 골라야하기때문에 for문 안에 조건문을 넣어주었다.
if(n % i === 0 && m % i ===0){ : 최대공약수이기때문에 n과 m이 모두 나머지가 0이 되는 경우만 고르면 된다.
근데 반복문이기 때문에 결국에는 가장 마지막에 들어가는 숫자만 들어가게된다.
예를들어 콘솔에 찍으면 1,3이 순서대로 찍히게 되는데 for문이기때문에 마지막 값인 3만 들어가게 됨!
그래서 최대공약수인 gcd에 넣어준다.
이제는 최소공배수를 구해야할 차례
이거는 몰랐는데, 두수의곱이 최대공약수와 최대공배수인지 몰랐다
두수의곱 = 최대공약수 * 최대공배수 이 공식도 문제 풀다가 발견함
그래서 lcm = (n * m) / gcd; 이렇게 최소공배수를 구한뒤 lcm에 넣어주었다.
그리고 answer배열에 넣어준뒤 return
CASE 1
function solution(n, m) {
// 최대공약수 : 두개 이상의 수가 공통으로 가지는 약수 중에서 가장 큰 수
// 최소공배수 : 두개 이상의 수가 공통으로 가지는 배수 중에서 가장 작은 수
// 최대공약수 구하기
let max = 0; // 공약수 중에서 제일 큰 값
for( let i = 1; i <= m; i++ ) {
if( n % i === 0 && m % i === 0 ) {
max = i;
}
}
// 최소공배수 구하기
let min = 0; // 공배수 중에서 제일 작은 값
for( let i = m; i <= n * m; i += m ) {
if( i % n === 0 ) {
min = i;
break;
}
}
return [ max, min ]
}
n % i === 0 && m % i === 0 n과 m을 나눴을때 나머지가 없어야 약수임.
for( let i = m; i <= n * m; i += m ) 초기값은 m으로 n,m중에 큰 값으로 시작하고
조건문은 m이 n * m을 넘는 수는 없기때문에 n * m으로 설정
제어문은 n*m으로 해준다.
증감문은 i+=m 으로 되어있는데 i++로 해도되지만 +=m 으로 하게 되면 m의 배수로 진행되기 때문에 조금 더 적은 반복을 돌릴 수 있다
function solution(n, m) {
// 최대공약수 : 두개 이상의 수가 공통으로 가지는 약수 중에서 가장 큰 수
// 최소공배수 : 두개 이상의 수가 공통으로 가지는 배수 중에서 가장 작은 수
// 최대공약수 구하기
let max = 0; // 공약수 중에서 제일 큰 값
for( let i = 1; i <= m; i++ ) {
if( n % i === 0 && m % i === 0 ) {
max = i;
}
}
// 최소공배수 구하기
let min = 0; // 공배수 중에서 제일 작은 값
for( let i = biggest; i <= n * m; i += biggest ) {
if( i % n === 0 ) {
min = i;
break;
}
}
return [ max, min ]
}
위 코드는 최댓값과 최솟값을 변수로 지정해준뒤 작성한 코드인데, case1과 비슷하다.
CASE 2
function solution(n, m) {
// 유클리드 호제법
// - 최대공약수를 구하기 위한 알고리즘 (공식)
// 1. a를 b로 나누었을 때, ( a > b, 큰 수를 더 작은 수로 나누었을 때 )
// 2-1. 나머지값(c)이 0이 되면, 작은 수(b)가 최대공약수가 된다.
// 2-2. 나머지값(c)이 0이 아니라면, b를 c로 나눈다. (1번 과정부터 반복)
// 반복 후 나머지 값이 0이 나오는 경우를 만난다면, 작은 수(b)가 최대공약수가 된다.
let a = Math.max( n, m ) // 큰 수
let b = Math.min( n, m ) // 작은 수
let c = 0; // a를 b로 나눴을 때의 나머지 값
while( a % b > 0 ) {
c = a % b // 큰 수에서 작은 수를 나눈 나머지 값을 저장
a = b; // 큰 수에는 나눴을 때의 더 작은 수를 가져온다.
b = c; // 작은 수에는 나머지 값을 가져온다.
}
// 최소공배수 : n과 m을 곱한 값을 최대공약수로 나눠준 값
return [ b, (n * m) / b ]
}
