[Algorithm] 숫자 카드 나누기 (Programmers - JavaScript)

문제 설명

철수와 영희는 선생님으로부터 숫자가 하나씩 적힌 카드들을 절반씩 나눠서 가진 후, 다음 두 조건 중 하나를 만족하는 가장 큰 양의 정수 a의 값을 구하려고 합니다.

 

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

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

 

에를 들어, 카드들에 10, 5, 20, 17이 적혀 있는 경우에 대해 생각해 봅시다. 만약, 철수가 [10, 17]이 적힌 카드를 갖고, 영희가 [5, 20]이 적힌 카드를 갖는다면 두 조건 중 하나를 만족하는 양의 정수 a는 존재하지 않습니다. 하지만, 철수가 [10, 20]이 적힌 카드를 갖고, 영희가 [5, 17]이 적힌 카드를 갖는다면, 철수가 가진 카드들의 숫자는 모두 10으로 나눌 수 있고, 영희가 가진 카드들의 숫자는 모두 10으로 나눌 수 없습니다. 따라서 철수와 영희는 각각 [10, 20]이 적힌 카드, [5, 17]이 적힌 카드로 나눠 가졌다면 조건에 해당하는 양의 정수 a는 10이 됩니다.

 

철수가 가진 카드에 적힌 숫자들을 나타내는 정수 배열 arrayA와 영희가 가진 카들에 적힌 숫자들을 나타내는 정수배열 arrayB가 주어졌을 때, 주어진 조건을 만족하는 가장 큰 양의 정수 a를 return 하도록 solution 함수를 완성해주세요. 만약, 조건을 만족하는 a가 없다면, 0을 return 해 주세요.

 

 

 

---

 

 

 

 

 

 

---

 

 

 

 

 

 

---

 

 

 

 

 

 

---

 

 

 

풀이:

이번 문제는 철수와 영희가 가지고 있는 카드들의 최대 공약수를 구하고, 최대 공약수로 상대방의 카드들을 나눠서 나머지가 0이 아닌 숫자들 중 제일 큰 숫자를 찾는 알고리즘이였다.

 

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

유클리드 호제법을 사용하여 철수와 영희의 카드들의 최대 공약수를 각각 찾길 위해서이다. 유클리드 호재법을 적용한 알고리즘 2가지로 표현했다.

function gcd(a, b) {
  if (b == 0) {
    return a;
  } else {
    return gcd(b, a % b);
  }
}
 
function gcd2(a, b) {
  while (b != 0) {
    let temp = b;
    b = a % b;
    a = temp;
  }
  return a;
}

 

나같은 경우에는 짧게 처리하기 위해 재귀를 사용하였다.

 

유클리드 호제법을 사용 후 철수의 최대 공약수로 영희의 숫자들을 나눌 수 있는지 비교해보았고, 영희의 최대 공약수로 철수의 숫자들을 나눌 수 있는지 비교를 해보았다. 서로소가 아닌 경우에는 최대값을 처리하는 리턴하는 방식으로 해결되었다.

const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b));
 
function solution(arrayA, arrayB) {
  let answer = 0;
 
  let a = arrayA[0];
  let b = arrayB[0];
  for (let i = 1; i < arrayA.length; ++i) {
    a = gcd(a, arrayA[i]);
    b = gcd(b, arrayB[i]);
  }
 
  b = b === 1 ? 0 : b;
  a = a === 1 ? 0 : a;
  const checkA = arrayA.every((value) => value % b !== 0);
  const checkB = arrayB.every((value) => value % a !== 0);
 
  if (checkA) {
    answer = Math.max(answer, b);
  }
  if (checkB) {
    answer = Math.max(answer, a);
  }
 
  return answer;
}

 

 

 

 

 

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/135807

프로그래머스