[programmers] 숫자 카드 나누기

📝 [Lv2] 숫자 카드 나누기

👀 문제 설명

철수와 영희는 선생님으로부터 숫자가 하나씩 적힌 카드들을 절반씩 나눠서 가진 후, 다음 두 조건 중 하나를 만족하는 가장 큰 양의 정수 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 해 주세요.

 

🚨 제한 사항

• 1 ≤ arrayA의 길이 = arrayB의 길이 ≤ 500,000
• 1 ≤ arrayA의 원소, arrayB의 원소 ≤ 100,000,000
• arrayA와 arrayB에는 중복된 원소가 있을 수 있습니다.

 

💻 입출력 예

arrayA	arrayB	result
[10, 17]	[5, 20]	0
[10, 20]	[5, 17]	10
[14, 35, 119]	[18, 30, 102]	7

 

✨ 풀이 설명

우선 값을 만족하는 가장 큰 수를 구해야하기 때문에 각 배열을 나눌 수 있는 가장 큰 수를 구해주었다.
각 배열을 나눌 수 있는 가장 큰 정수는, 해당 배열의 가장 작은 값이다. 이 값보다 커지면 그 값보다 작은 값들은 나눌 수 없기 때문이다.
처음에는 최솟값을 Math.min()을 사용해 구해주려고 하였으나, 배열의 길이가 긴 탓에 가능한 스택 크기를 초과하게 되어 에러를 호출하였다. (동일한 에러)
그래서 배열을 오름차순 정렬하여 0번 index를 사용하기로 하였다.

만족하는 두 조건의 로직이 동일하므로, 같은 결과를 도출하는 calc()라는 함수를 생성하였다.
calc() 함수는 두 배열을 전달받아 기준 배열의 최솟값부터 1까지 조건을 만족하는지 검사하는 로직을 담고 있다.
기준 배열은 모두 나눠져야 하므로 some을 사용해 하나라도 나머지가 생기는, 나눠지지 않는 수가 있는지 확인해 주었다. 
타깃이 되는 배열은 나눠지는 수가 있으면 안 되기 때문에 모두 나눠지지 않는 수인지를 확인해 주었다.
큰 수부터 검사를 하기 때문에 만약 두 조건을 모두 만족한다면 바로 반환해 주었고, 모든 수를 검사했는데도 만족하는 수가 없다면 0을 반환해 주었다.

두 함수에 각각 기준이 되는 배열과 타깃 배열을 넣어 두 조건 중, 더 큰 수를 반환해 결과를 도출해 주었다.

 

🕵️‍♂️ 코드

 

function solution(arrayA, arrayB) {

  arrayA.sort((a, b) => a - b);

  arrayB.sort((a, b) => a - b);

  const calc = (standard, target) => {

    for (let std = standard[0]; std > 0; std--) {

      if (!standard.some(arr => arr % std) && target.every(arr => arr % std)) return std;

    }

    return 0;

  }

  return Math.max(calc(arrayA, arrayB), calc(arrayB, arrayA));

}