Programmers / Level 2 / 숫자 카드 나누기 / JS

문제 간단설명

철수와 영희는 숫자 카드를 절반씩 나눠갖는다. 그리고 다음 두 조건 중 하나를 만족하는 가장 큰 양의 정수 a의 값을 구하려한다.

1. 철수가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고, 영희가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수
2. 영희가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고, 철수가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수

위 조건을 만족하는 정수 중에서 가장 큰 양의 정수 a를 반환하면 된다.

만약 조건을 만족하는 a가 없다면 0을 반환한다.

 

제한 사항

• 1 <= arrayA의 길이 = arrayB의 길이 <= 500,000
• 1 <= arrayA의 원소, arrayB의 원소 <= 100,000,000
• arrayA와 arrayB에는 중복된 원소가 있을 수 있음

 

성공 코드

function solution(arrayA, arrayB) {
  let result = 0;

  /**
   * 두 정수를 인자로 받아 최대공약수를 반환하는 함수이다.
   *
   * @param {number} a 정수1
   * @param {number} b 정수2
   * @returns 두 정수의 최대공약수
   */
  const getGCD = (a, b) => {
    if (b === 0) {
      return a;
    }

    return getGCD(b, a % b);
  };

  /**
   * 정수 배열을 받아서, 배열안의 숫자들에 대한 최대공약수를 반환하는 함수이다.
   *
   * @param {number[]} array
   * @returns 배열에 있는 숫자들의 최대공약수
   */
  const getGCDOfArray = (array) => {
    // 만약 배열에 요소가 1개만 있다면, 그 값 자체가 최대공약수이다.
    if (array.length === 1) {
      return array[0];
    }

    let result = array[0];
    for (let i = 0; i < array.length; i++) {
      result = getGCD(result, array[i]);
    }

    return result;
  };

  const gcdA = getGCDOfArray(arrayA);
  const gcdB = getGCDOfArray(arrayB);

  // 배열의 최대공약수가 1이라는 말은, 1보다 큰 공약수가 없다는 뜻이다.
  // arrayA의 최대공약수로 arrayB에 나누어 떨어지는 수가 없다면,
  // 조건을 만족하므로 저장되어 있는 결과값의 최대값을 갱신한다.
  if (gcdA !== 1 && arrayB.every((el) => el % gcdA !== 0)) {
    result = Math.max(result, gcdA);
  }

  // arrayB의 최대공약수로 arrayA에 나누어 떨어지는 수가 없다면,
  // 조건을 만족하므로 저장되어 있는 결과값의 최대값을 갱신한다.
  if (gcdB !== 1 && arrayA.every((el) => el % gcdB !== 0)) {
    result = Math.max(result, gcdB);
  }

  return result;
}

 

 

이 문제에서 배열의 모든 정수가 나누어 떨어지는 양의 정수, 그리고 답은 그 중에서 가장 큰 수를 반환해야 한다. 즉, 공약수중에서 제일 큰 최대공약수를 반환하는 문제이다.

 

최대공약수를 구하기 위해서 '유클리드 호제법'을 사용하였다.

(유클리드 호제법을 이용해서 푼 문제이다. 유클리드 호제법에 대한 설명도 적어놓았다.)

백준 / 수학 / 2609번 / 최대공약수와 최소공배수 / C++

 

최대공약수는 무조건 1이상 나오게 되어있다. 왜냐하면 모든 양의 정수는 1로 나누어지기 때문이다.

하지만 그럴 경우, 다른 배열도 1로 모두 나누어 떨어지기 때문에 조건에 부합하지 않는다.

그러므로 현재 배열에서 1보다 큰 최대공약수를 구하고, 그 값이 다른 배열에 있는 수들의 약수가 되지 않는다면 정답이다.

 

이때 Array method의 every() 함수를 사용하였다. every()는 인자로 들어오는 callback 함수에 대해 모두 true라면 true, 하나라도 false 값을 가진다면 그 즉시 멈추고 false를 반환한다.

(JS의 여러 배열 메서드에 대해 작성한 글이다. 생각보다 유용한 메서드가 많다.)

Array Method

 

각각에 대해서 조건 검사를 해준다음에, 결과값을 반환해주었다.