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

이명진·2022년 9월 17일
0

코드카타

목록 보기
43/68

문제요약

두수를 받아서 두수의 최대공약수와 최소공배수를 리턴하면 된다.
최대 공약수와 최소공배수 오래간만에 봐서 정확한 정의를 찾아보았다.
거기서 힌트를 좀 얻어서 최소공배수는 두자연수의 곱 / 최대공약수 라는 것을 알게 되었고
최대공약수는 유클리드 호제법을 이용하면 시간복잡도를 줄일수 있다는 것을 알게 되었다.

일단 정의로는 최대공약수는 두 자연수의 공통된 약수중 가장 큰수 이다
최소 공배수는 두자연수의 공통된 배수 중에 가장 작은수 이다.

일단 최대공약수를 구하면 최소공배수는 쉽게 풀린다는 이야기이다.

최대공약수 는 두수가 A,B가 있을때
두수의 몫을 구하고 A는 B가 되어서 두수의 몫과 계속 몫을 구하면 0이 되는 이전의
B가 최소공배수가 된다.

말은 어렵지만 잘 나와 있고 힌트를 얻은 분의 주소를 첨부한다.
https://myjamong.tistory.com/138

내가푼 풀이

내가 푼 로직은 이렇다.

function solution(n, m) {
    var answer = [];
  let A= n;
  let B= m;
  let last = 0;
  while(B>0){
   last = A%B;
    A=B;
   B=last;
    console.log(A)
  }
answer.push(A);
answer.push(n*m/A)
  
    return answer;
}

두수를 n,m에 저장했고 last 는 두수의 A,B의 몫이다.
계속 바꿔주면서 0이 되기 이전의 몫을 리턴했다.

다른사람의 풀이

다른사람의 풀이이다. 대부분 유클리드 호재법을 이용한것 같다.
함수 두개를 이용해서 푼사람도 있고 다양한데
특이하게 for 문을 사용하신 분이 있어 그 분의 로직을 적어본다

function gcdlcm(a, b) {
    var r;
    for(var ab= a*b;r = a % b;a = b, b = r){}
    return [b, ab/b];
}

for문을 많이 쓰지만 for문 조차 제대로 이해못했다는 것을 알게 되었다.
조건 문만 으로도 for문을 사용할수 있다는 것을 알수 있었다.
하지만 var를 쓴다는 점에서 잘짜여지 코드는 아닌 것 같다.
for 문의 var ab 를 let ab로 변경하면 에러가 뜬다.

새로운 것을 접한다.

profile
프론트엔드 개발자 초보에서 고수까지!

0개의 댓글