프로그래머스 LV2 "N개의 최소공배수"

프로그래머스 LV2 N개의 최소공배수

기초부터 다시 공부를 하기위해 프로그래머스 라는 사이트에서 코딩테스트를 LV0 부터 가능한곳까지 못하는곳은 레퍼런스를 찾아가며 풀어보려고 합니다.

매일 1개의 풀이를 하고 그 풀이에대한 나의 생각 및 해석을 적어보려합니다.

오늘은 LV2 문제 ‘N개의 최소공배수’ 문제입니다.

위 이미지가 프로그래머스 코딩문제입니다.

문제는 매개변수로 arr가 주어집니다. arr안에 n개의 숫자가 있고 그 수들의 최소 공배수를 출력하는 문제입니다.

그럼 오늘의 문제를 한번 풀어보겠습니다.

기본 세팅 코드도 알아보겠습니다.

function solution(arr) {
  var answer = 0;
  return answer;
}

기본 세팅 코드는 매개변수 arr이 입력되고 함수 안에는 answer이라는 변수가 선언되어 리턴하는 간단한 기본 세팅 코드입니다.

오늘 문제중 공배수가 무엇인지 우선 알아보고 문제를 풀어보도록 하겠습니다.

공배수

공배수는 두 개 이상의 숫자의 배수 중에서 공통으로 존재하는 배수를 의미합니다. 다시 말해, 두 수의 공배수는 각각의 수로 나눌 수 있는 숫자입니다.

예를 들어, 두 숫자 4와 6의 배수들을 생각해봅시다:

4의 배수: 4, 8, 12, 16, 20, 24, … 6의 배수: 6, 12, 18, 24, 30, … 위 두 배수에서 공통으로 나타나는 숫자들을 공배수라고 합니다. 여기서는 12, 24, … 등이 공배수가 됩니다.

최소공배수 (Least Common Multiple, LCM) 최소공배수는 두 개 이상의 숫자들 중에서 가장 작은 공배수를 의미합니다. 예를 들어, 4와 6의 최소공배수를 구해봅시다:

4의 배수: 4, 8, 12, 16, 20, 24, … 6의 배수: 6, 12, 18, 24, 30, … 공통으로 나타나는 가장 작은 숫자는 12이므로, 4와 6의 최소공배수는 12입니다.

다수의 숫자의 최소공배수 n개의 숫자가 주어졌을 때, 이들 숫자들의 최소공배수는 모든 숫자의 배수 중에서 가장 작은 공배수입니다. 예를 들어, 2, 3, 4의 최소공배수를 구해봅시다:

2의 배수: 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, … 3의 배수: 3, 6, 9, 12, 15, 18, 21, 24, … 4의 배수: 4, 8, 12, 16, 20, 24, … 이 세 숫자의 배수 중 공통으로 나타나는 가장 작은 숫자는 12입니다. 따라서, 2, 3, 4의 최소공배수는 12입니다.

여러 수의 최소공배수를 구할 때는 두 수씩 차례로 최소공배수를 구해 나가면 됩니다. 예를 들어, 세 수 a, b, c의 최소공배수는 다음과 같이 구할 수 있습니다:

먼저 a와 b의 최소공배수를 구합니다. 구한 최소공배수와 c의 최소공배수를 다시 구합니다. 이 방법을 모든 수에 대해 반복하면 최종적으로 n개의 수의 최소공배수를 구할 수 있습니다.

이렇게 공배수에 대해 한번 알아보았습니다.

그럼 오늘 문제의 풀이를 코드로 한번 작성해 보겠습니다.

function solution(arr) {
  function gcd(a, b) {
    while (b !== 0) {
      let temp = b;
      b = a % b;
      a = temp;
    }
    return a;
  }

  function lcm(a, b) {
    return (a * b) / gcd(a, b);
  }

  return arr.reduce((acc, cur) => lcm(acc, cur), 1);
}

위 코드의 간단한 설명을 알려드리겠습니다.

1. 최대공약수 함수 (gcd)
   • 두 수 a와 b를 입력받아 유클리드 호제법을 사용해 최대공약수를 계산합니다. b가 0이 될 때까지 a를 b로 나눈 나머지를 b에 할당하고, a와 b를 교체하는 과정을 반복합니다.
2. 최소공배수 함수 (lcm)
   • 두 수 a와 b를 입력받아 최대공약수 함수를 사용해 최소공배수를 계산합니다. 공식은 (a * b) / gcd(a, b)입니다.
3. 배열의 최소공배수를 계산
   • arr.reduce 메서드를 사용해 배열의 모든 요소에 대해 최소공배수를 누적 계산합니다. 초기값은 1로 설정합니다.

그럼 코드를 프로그래머스에 한번 확인해보겠습니다.

성공이네요!

오늘은 프로그래머스 LV2 ‘N개의 최소공배수’ 문제의 대해서 알아봤습니다.

제 방법이 꼭 정답은 아니니 그저 이런방법도 있구나하고 참고용으로만 봐주시면 감사하겠습니다.

감사합니다.