프로그래머스 / 최대공약수 최소공배수
🚀 문제
-
문제 링크 : 프로그래머스 1단계 최대공약수와 최소공배수
-
설명 : 두 수를 입력받아 [최대공약수, 최소공배수] 를 리턴한다.
-
입출력 예시 :
3, 12 => [3, 12]
2, 5 => [1, 10]
4, 6 => [2, 12]
🚀 풀이 설명
최대공약수 : 0이 아닌 두 개 이상의 정수의 공통되는 약수 중에서 가장 큰 수 (지식백과 출처)
우선 최대공약수를 먼저 구했다.
주어진 두 수중에 큰 수와 작은 수를 구분한다. (4, 6 이 들어오는 경우)
최대공약수는 공통되는 약수여야 해서 작은 수보다 클 수 없다. (최대공약수는 4 이하의 숫자이다.)
작은 수 이하이기 때문에 두 수를 각각 작은 수로 나눠서 둘 다 나머지가 0이 되는지 확인했다.
(4는 4로 딱 떨어진다. 6은 4로 딱 떨어지지 않는다.)
둘다 딱 떨어지지 않는다면, 작은 수에서 -1 을 한 수로 다시 시도한다.
(4는 3으로 딱 떨어지지 않는다.)
(4는 2로 딱 떨어진다. 6은 2로 딱 떨어진다. 그러므로 4, 6의 최대공약수는 2이다)
이걸 작은 수가 1이 될 때까지 반복하고, 1까지 내려오면 1이 최대공약수이다.
최소공배수 : 두 개 이상의 자연수의 공통인 배수 중 가장 작은 수
우선 큰 수를 작은 수로 나눴을 때 딱 떨어지면 큰 수가 최소 공배수가 된다.
떨어지지 않는 경우를 계산해보자.
최소공배수는 2*2
과 2*3
의 최대 공배수는 2*2*3
이다.
우리는 이미 최대공약수가 2라는 것을 위에서 구했다.
따라서 4와 6을 곱한 수에서 최대공약수인 2로 나눈 수가 최소공배수이다.
다른 예시로 2*5
, 3*5
의 최대공약수는 5.
최소공배수는 2*5*3*5/5
. 즉 30 이다.
🚀 코드
function solution(n, m) {
let big = n > m ? n : m
let small = n < m ? n : m
let answer = [];
// 최대공약수
for (let i = small; i > 0; i--) {
if (big % i === 0 && small % i === 0) {
answer.push(i)
break
}
}
// 최소공배수
if (big % small === 0) {
answer.push(big)
} else {
answer.push(big * small / answer[0])
}
return answer;
}
Author And Source
이 문제에 관하여(프로그래머스 / 최대공약수 최소공배수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@flobeeee/프로그래머스-최대공약수-최소공배수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)