프로그래머스 Lv.2 숫자 카드 나누기
문제 설명
철수와 영희는 선생님으로부터 숫자가 하나씩 적힌 카드들을 절반씩 나눠서 가진 후, 다음 두 조건 중 하나를 만족하는 가장 큰 양의 정수 a의 값을 구하려고 합니다.
- 철수가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고 영희가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a
- 영희가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고, 철수가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 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,000arrayA와arrayB에는 중복된 원소가 있을 수 있습니다.입출력 예
arrayA arrayB result [10, 17] [5, 20] 0 [10, 20] [5, 17] 10 [14, 35, 119] [18, 30, 102] 7
풀이 코드
function solution(arrayA, arrayB) {
const getGCD = (nums) => {
return nums.reduce((a, b) => {
while (b !== 0) {
let temp = b;
b = a % b;
a = temp;
}
return a;
});
};
const getDivisor = (num) => {
let divisors = [];
for (let i = 2; i <= Math.sqrt(num); i++) {
if (num % i === 0) {
divisors.push(i);
if (i !== num / i) divisors.push(num / i);
}
}
if (num !== 1) divisors.push(num);
return divisors.sort((a, b) => b - a);
};
const isValid = (divisors, arr) => {
for (let i = 0; i < divisors.length; i++) {
let answer = 0;
for (let j = 0; j < arr.length; j++) {
if (arr[j] % divisors[i] === 0) {
answer = 1;
break;
}
}
if (answer === 0) return divisors[i];
}
};
const divisorsA = getDivisor(getGCD(arrayA));
const divisorsB = getDivisor(getGCD(arrayB));
const a = isValid(divisorsA, arrayB) || 0;
const b = isValid(divisorsB, arrayA) || 0;
return a >= b ? a : b;
}
풀이 설명
전체 수들의 최대 공약수의 약수는 모두 공약수이다.
function solution(arrayA, arrayB) {
const getGCD = (nums) => {
return nums.reduce((a, b) => {
while (b !== 0) {
let temp = b;
b = a % b;
a = temp;
}
return a;
});
};
//...
}
getGCD는 매개변수로 받은 숫자 배열의 최대 공약수를 구하는 함수이다.
-
루프 내에서
a를b로 나눈 나머지를b에 할당하고,a는 이전의b값을 재할당한다. -
이 과정을 반복해서
b가 0이 되면,a는 두 수의 최대공약수이다.
function solution(arrayA, arrayB) {
//...
const getDivisor = (num) => {
let divisors = [];
for (let i = 2; i <= Math.sqrt(num); i++) {
if (num % i === 0) {
divisors.push(i);
if (i !== num / i) divisors.push(num / i);
}
}
if (num !== 1) divisors.push(num);
return divisors.sort((a, b) => b - a);
};
//...
}
getDivisor는 1을 제외한 모든 약수를 내림차순으로 정렬한 배열을 리턴한다.
내림차순으로 정렬하는 이유는 상대의 카드와 약수를 비교하는 과정에서 가장 큰 수를 빠르게 구하기 위함이다.
function solution(arrayA, arrayB) {
//...
const isValid = (divisors, arr) => {
for (let i = 0; i < divisors.length; i++) {
let answer = 0;
for (let j = 0; j < arr.length; j++) {
if (arr[j] % divisors[i] === 0) {
answer = 1;
break;
}
}
if (answer === 0) return divisors[i];
}
};
//...
}
isValid는 아까 getDivisor로 구한 약수 배열과 상대의 카드 배열을 매개변수로 받아 비교한다.
- 약수 배열(=divisors)을 순회하면서 상대의 카드에 적힌 숫자들을 모두 나눌 수 없는 약수 중 가장 큰 수를 구한다.
function solution(arrayA, arrayB) {
//...
const divisorsA = getDivisor(getGCD(arrayA));
const divisorsB = getDivisor(getGCD(arrayB));
const a = isValid(divisorsA, arrayB) || 0;
const b = isValid(divisorsB, arrayA) || 0;
return a >= b ? a : b;
}
divisorsA와 divisorsB는 각각 철수와 영희의 카드 숫자들을 나눌 수 있는 정수들의 배열(공약수)이다.
a와 b에는 isValid 값을 저장한다. 단, isValid 값이 undefined인 경우(조건을 만족하는 정수가 없으면) 0을 저장한다.
a와 b를 비교하여 더 큰 수를 리턴한다.
References
프로그래머스 연습