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

Janet·2023년 3월 9일
0

Algorithm

목록 보기
65/314

문제 설명

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

제한 사항

  • 두 수는 1이상 1000000이하의 자연수입니다.

입출력 예

nmreturn
312[3, 12]
25[1, 10]

입출력 예 설명

입출력 예 #1위의 설명과 같습니다.

입출력 예 #2자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.


문제풀이

💡 문제풀이 과정

  • 약수는 어떤 수를 나누었을 때 나누어 떨이지게 하는 자연수이다. 따라서 for() 반복문을 이용하여 주어진 자연수 number % i === 0이면 약수이다. 따라서 주어진 두 수(nm)의 공약수를 구하는 것은 if (n % i === 0 && m % i === 0)가 될것이다. 나는 빈 배열에 공약수들을 담아주었고, 최대공약수는 공약수가 담긴 배열의 마지막 인덱스 값이 될 것이다. const 최대공약수 = arr[arr.length -1];
  • 마지막으로 최소공배수를 구하는 방법으로 공약수를 이용하는 방법과 소인수분해하여 지수를 이용하는 방법이 있는데, 나는 공약수를 이용하는 방법을 사용하였다. 두 수를 서로소(공통된 약수가 없는 수)가 나올 때까지 계속 공약수로 나누어 공약수에 서로소까지 곱하는 방법이다. 따라서 코드는 const 최소공배수 = 최대공약수 * (n / 최대공약수) * (m / 최대공약수); 이렇게 만들었다.
  • 답안 2번의 경우 다른 사람의 풀이인데, for() 반복문 범위를 i = n과 m의 최소값부터 시작하여 i > 0 그리고 i--으로 설정하였다. (나의 경우 주어진 자연수가 1000000이하의 수라고 해서 최대 범위를 너무 높게 잡아놨기 때문에…) 그리고 이렇게 범위를 설정하게 되면, 답안 1번과 같이 공약수를 빈 배열에 담아 최대공약수를 추출할 필요없이, 최대공약수를 for()문 속에서 바로 뽑을 수 있겠다.

❓ 약수 / 공약수 / 서로소 / 최대공약수/ 최소공배수의 기본 이론 및 예제

  • 약수: 어떤 수를 나누었을 때 나누어 떨어지게 하는 자연수.
  • 공약수: 서로 다른 두 자연수의 공통된 약수.
    • 3의 약수: 1, 3
    • 12의 약수: 1, 2, 3, 4, 6, 12
    • 3과 12의 공약수: 1, 3
  • 최대공약수: 공약수에서 제일 큰 수로, 위 예시에서 최대공약수는 3이 되겠다.
  • 참고로 공약수가 없는 경우가 있는데, 이처럼 공통된 약수가 없는 수를 '서로소'라고 한다.
  • 공배수: 서로 다른 두 자연수의 공통된 배수.
    • 2의 배수: 2, 4, 6, 8, 10, 12, 14, 16, 18, ...
    • 3의 배수: 3, 6, 9, 12, 15, 18, 21, ...
    • 2와 3의 공배수: 6, 12, 18 ...
  • 최소공배수: 공배수에서 제일 작은 수로, 위 예시에서 최소공배수는 6이 되겠다.

 답안 #1

function solution(n, m) {
  let answer = [];
  let arr = [];
  for (let i = 1; i <= 1000000; i++) {
    if (n % i === 0 && m % i === 0) arr.push(i); //공약수 배열에 담기
  }
  const max = arr[arr.length - 1]; //최대공약수
  const min = max * (n / max) * (m / max); //최소공배수
  answer.push(max, min);
  return answer;
}

 답안 #2

function solution(n, m) {
  const min = Math.min(n, m);
  let common_max = 1;
  for(let i = min; i > 0; i--){
      if(n % i === 0 && m % i === 0){
          common_max = i;
          break;
      }
  }
  return [common_max, common_max * (n / common_max)* (m / common_max)];
}
profile
😸

0개의 댓글