[프로그래머스 lv2] 숫자 카드 나누기

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

 

 

---

 

우선 두가지 경우가 있다

 

1. 철수는 모두 나눠지는데 영희는 모두 안 나눠지는 경우

2. 철수는 모두 안 나눠지는데 영희는 모두 나눠지는 경우

 

 

처음에는 철수, 영희 각각의 최대공약수를 구하고 그것이 상대방의 수를 모두 나눌 수 있는지를 확인하려고 했다

하지만 만약 상대방의 수가 하나라도 나눠진다면 다음 최대공약수를 찾아야하고 log(min(a, b))또 다시 상대방의 배열을 순회 log(n) 하며 확인해야한다. 하지만 이렇게 한다면 제한사항 케이스일때 시간초과가 날 것이다.

 

 

사실 문제가 원하는 조건을 잘 뜯어보면 a의 범위를 확 줄일 수 있다

위의 첫번째 경우에서 "철수배열의 수를 모두 나눌있는 수 a" => 철수배열의 최소값도 나눠야하므로 a의 최대값은 철수배열의 최소값이다.

또한 공약수는 1이 될 수 없다 (1은 철수, 영희 둘의 공약수이기 때문이다)

따라서 검사해야할 수의 범위는 [2 ~ 철수배열의 최소값]  으로 줄일 수 있다.

 

 

줄인 범위를 순회하며 상대방 배열의 모든 숫자를 나눌 수 없는 a를 구한다.이때 every메서드를 쓰면 간편하게 검사할 수 있다.

배열.every

배열의 각 요소가 주어진 조건을 만족하는지 확인하는 메서드이다.

배열의 모든 요소가 주어진 조건을 만족하면 true를 반환하고,

조건을 만족하지 않는 요소가 하나라도 있으면 false를 반환한다

 

 

---

전체코드 

function solution(arrayA, arrayB) {
    var answer = 0;
    arrayA.sort((a, b) => a-b);
    arrayB.sort((a, b) => a-b);
    return Math.max(findA(arrayA, arrayB), findA(arrayB, arrayA));
}

function findA(canDivide, cantDivide) {
    const maxGCD = canDivide[0];
    for (let i = maxGCD; i > 1; --i) {
        if (canDivide.every(d => d % i === 0) && cantDivide.every(d => d % i !== 0)) {
            return i;
        }
    }
    return 0;
}

 

 

 

---

두번째 풀이 

문제요점

• 조건중 하나를 만족하는 가장 큰 양의 정수리턴
• 조건1: 철수의 숫자를 모두 나눌 수 있고, 영희의 수를 하나도 나눌 수 없는 수
• 조건2: 조건1반대

 

문제풀이

• canDivide의 최대공약수가 1이거나 cantDivide 중 하나라도 나눌 수 있으면 0리턴
• 아니면 공약수 리턴
• 두 조건 중 큰 수 리턴

 

// 조건중 하나를 만족하는 가장 큰 양의 정수리턴
// 조건1: 철수의 숫자를 모두 나눌 수 있고, 영희의 수를 하나도 나눌 수 없는 수
// 조건2: 조건1반대
function solution(arrayA, arrayB) {
    arrayA.sort((a, b) => a-b);
    arrayB.sort((a, b) => a-b);
    
    return Math.max(findA(arrayA, arrayB), findA(arrayB, arrayA));
}

function findA(canDivide, cantDivide) {
    // 나눌 수 있는 그룹의 최대공약수구하기
    let gcd = canDivide[0];
    for (let i = 0; i < canDivide.length; i++) {
        gcd = getGCD(canDivide[i], gcd);
    }
    if (gcd === 1) return 0;
    // 공약수가 1이거나 cantDivide를 나눌 수 있으면 O리턴
    for (const e of cantDivide) {
        if (e % gcd === 0) {
            console.log(e % gcd)
            return 0;
        }
    }
    return gcd;
}

function getGCD(a, b) {
    const remainder = a % b;
    if (remainder === 0) return b;
    return getGCD(b, remainder);
}