programmers 코딩테스트 : 최대공약수와 최소공배수

H·2022년 5월 6일
0

Coding Test

목록 보기
8/26

🔔 최대공약수와 최소공배수

📢 문제 설명
두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

⛔ 제한 사항
두 수는 1이상 1000000이하의 자연수입니다.


유클리드 호제법
📍 숫자 a,b는 a>b, b/a의 나머지가 r인 경우
a와 b의 최대공약수 = b와 r의 최대 공약수
r= 0일때 b가 최대공약수 r= 0인경우 b/r로 나는 나머지 r0을 반복하여 나머지가 0이 되는 경우 나누는 수가 a,b의 최대 공약수 이다.

🔠 첫번쨰 시도한 코드 (통과 X)

function solution(n, m) {
    let answer = [];
    let min = m > 0 && n > 0 ? Math.min(m, n) : null;
    let max = m > 0 && n > 0 ? Math.max(m, n) : null;
    answer[0] = gcd(min, max);
    answer[1] = lcm(min, max);
    return answer;
}
function gcd(min, max) {
    if (max % min === 0) {
        return min;
    } else {
        while (min > 0) {
            let val = max % min;
            max = min;
            min = val;
            return val;
        }
    }
}
function lcm(min, max) {
    return Math.floor(
        gcd(min, max) * (min / gcd(min, max)) * (max / gcd(min, max))
    );
}

📌코드 설명

  1. 두 수중 작은 수 큰 수를 구한다. 0보다 작은 경우에는 null 처리
  2. gcd (최대공약수)는 max / min으로 나눴을 때 나머지가 없는 경우는 작은 수가 최대공약수
    1. 나머지가 0보다 큰 경우는 나머지가 0이 될 때까지 큰 수와 작은 수를 나눈다.
    2. 이때 큰 수는 min 값 작은 수는 나머지 값
    3. 나머지가 0이 될때까지 반복
  3. answer 순서 맞춰서 push

👀.....

테스트가 반만 통과한다.. else 잘못 쓴 것 같다..

🍀 피드백

다 시 짜 세 욧 .... 엉망이에요~ 피드백 해줄 것도 없음

🔠 두번째로 시도! 통과한 코드

function solution(n, m) {
  let answer = [];
  let min = Math.min(m, n);
  let max = Math.max(m, n);
  answer[0] = gcd(min, max);
  answer[1] = (min * max) / answer[0];
  return answer;
}
function gcd(min, max) {
  if (Math.floor(max % min) === 0) {
    return min;
  } else {
    while (max / min > 1) {
      let num = max % min;
      max = min;
      min = num;
      if (num === 0) break;
    }
    return max;
  }
}

📌 코드 설명

  1. min, max 값은 조건문으로 만들 필요가 없다. 둘 중 조건에 맞는 수만 담으면 된다.
  2. 소수점으로 떨어지는 경우 Math.floor로 처리 (반내림)
  3. while (조건은 무조건 참이어야 실행됩니다.)
    1. max와 min의 나머지 값을 num에 담는다.
    2. num의 값이 0인 경우 멈춤
    3. max는 min이 였던 값이 되고, min은 나머지가된다.
    4. 0이 될 때까지 돌가가 0이 되면 return max;

🍀 피드백

  1. 두개 다 구하는데 너무 오래걸림
  2. 응용력 키워야겠다
  3. 두개 다 구하는데는 유클리드 호제법이 가장 적합하다!

🔠 번외 코드 > 유클리드 호제법 & 근본

function solution(n, m) {
   let answer = [];
   let flag = n > m;
   let big = flag ? n : m;
   let small = flag ? m : n;
 
   flag = true;
 
   while (flag) { // true 라서 무조건 적으로 돌음
     const left = big % small; // 큰수 / 작은수의 나머지  
   //left = big(samll이었던 것) % small (left였던 것)
     flag = left != 0; //flag에 left !=0 일때 의 true false 값을 담음
 
     if (flag) { // if(true)일 때 
       big = small;  // 그 중 작은 수 
       small = left; // 작은 수에는 나머지 값 
     }
   }
   
   answer.push(small); // push는 선입 선출  
   answer.push((n * m) / small);
   
   return answer;
 }

🔠 번외 코드 > 유클리드 호제법 & 재귀호출

function solution(n, m) {
  let flag = n > m;
  let big = flag ? n : m;
  let small = flag ? m : n;

  const min = recursion(big, small);
  const max = (n * m) / min;

  return new Array(min, max);
}

function recursion(big, small) {
  const remainder = big % small;

  return remainder > 0 ? recursion(small, remainder) : small;
}
profile
🤘 돌머리도 ROCK이다! 🤘

0개의 댓글