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

4760 단어 2021.102021.10

​🚀 문제

​🚀 풀이 설명

최대공약수 : 0이 아닌 두 개 이상의 정수의 공통되는 약수 중에서 가장 큰 수 (지식백과 출처)

우선 최대공약수를 먼저 구했다.
주어진 두 수중에 큰 수와 작은 수를 구분한다. (4, 6 이 들어오는 경우)
최대공약수는 공통되는 약수여야 해서 작은 수보다 클 수 없다. (최대공약수는 4 이하의 숫자이다.)
작은 수 이하이기 때문에 두 수를 각각 작은 수로 나눠서 둘 다 나머지가 0이 되는지 확인했다.
(4는 4로 딱 떨어진다. 6은 4로 딱 떨어지지 않는다.)
둘다 딱 떨어지지 않는다면, 작은 수에서 -1 을 한 수로 다시 시도한다.
(4는 3으로 딱 떨어지지 않는다.)
(4는 2로 딱 떨어진다. 6은 2로 딱 떨어진다. 그러므로 4, 6의 최대공약수는 2이다)
이걸 작은 수가 1이 될 때까지 반복하고, 1까지 내려오면 1이 최대공약수이다.

최소공배수 : 두 개 이상의 자연수의 공통인 배수 중 가장 작은 수

우선 큰 수를 작은 수로 나눴을 때 딱 떨어지면 큰 수가 최소 공배수가 된다.

떨어지지 않는 경우를 계산해보자.
최소공배수는 2*22*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;
}

좋은 웹페이지 즐겨찾기