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

문제출처
https://school.programmers.co.kr/learn/courses/30/lessons/135807

문제 설명

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

입출력 예

문제풀이

1. 철수,영희가 가진 카드들에 적힌 모든 숫자를 나눌수 있는 양의 정수를 구하기 위하여 배열의 최대공약수를 구한다.
2. 최대공약수의 약수를 구하여 약수 중 큰 수부터 차례대로 상대의 숫자를 나눌 수 없는 지 확인한다.
   2-1. 나눌 수 없다면 그 수를 최대공약수로 설정하고 반복문을 빠져나온다.
   2-2. 나눌 수 있다면 다음 수를 확인하여 최대공약수를 변경해준다.
3. 철수, 영희의 최대공약수가 모두 1이라면 본인이 가진 최대공약수는 상대의 카드를 나눌 수 있다는 뜻이기 때문에 조건에 만족하는 것이 없다. 그러므로 1을 리턴한다.
4. 철수의 최대공약수, 영희의 최대공약수 중 최댓값을 정답으로 리턴한다.

코드

function solution(arrayA, arrayB) {
    var answer = 0;
    arrayA.sort((a,b) => a-b);
    arrayB.sort((a,b) => a-b);
    
    //최대공약수
    let gcdA = arrayA[0];
    let gcdB = arrayB[0];
    for(let i in arrayA) gcdA = gcd(gcdA, arrayA[i]);
    for(let i in arrayB) gcdB = gcd(gcdB, arrayB[i]);
    
    //약수구하기
    let arrA = arr(gcdA);
    let arrB = arr(gcdB);
    
    for(let v of arrA){
        gcdA = v;
        var rest;
        for(let b of arrayB){
            rest = b%v;
            if(rest == 0) break;
        }
        
        if(rest != 0) break;
    }
    
   for(let v of arrB){
        gcdB = v;
        var rest;
        for(let a of arrayA){
            rest = a%v;
            if(rest == 0) break;
        }
       if(rest != 0) break;
    }
    
    if(gcdA == 1 && gcdB == 1) return 0;
    return Math.max(gcdA, gcdB);
    
}
let arr = (num) => {
    let result = [];
    let idx = 1;
    while(idx <= Math.sqrt(num)){
        if(num % idx == 0){
            result.push(idx);
            if(num / idx != idx) result.push(num / idx);
        }
        idx++;
    }
    result.sort((a,b) => b-a);
    return result;
}
let gcd = (num1, num2) => {
    while(num2 > 0){
        let r = num1 % num2;
        num1 = num2;
        num2 = r;
    }
    return num1;
}

리팩토링

function solution(arrayA, arrayB) {
    return Math.max(getAnswer(arrayA, arrayB), getAnswer(arrayB, arrayA));
}

let getAnswer = (arr1, arr2) => {
    let gcd = (a, b) => (a%b == 0 ? b : gcd(b, a%b));
    let ele = arr1[0]; 
    for(let v of arr1) ele = gcd(ele, v); // 최대공약수
    let gcdArr = arr(ele); // 공약수
    for(let v of gcdArr) if(arr2.every(b => b%v != 0)) return v;
    return 0;
}

let arr = (num) => {
    let result = [];
    for(let i=1; i<=Math.sqrt(num); i++){
        if(num%i==0){
            result.push(i);
            if(num/i!=i) result.push(num/i);
        }
    }
    return result.sort((a,b) => b-a);
}

every 사용해서 리팩토링하니 시간이 많이 단축되었는데 시간복잡도 확인해보니까 O(n)이다. every때문에 시간이 줄어든 거 같진 않은데 어디서 시간이 줄었는 지 모르겠다.

다른 사람 코드

function solution(arrayA, arrayB) {
    const aResult = getAnswer(arrayA, arrayB)
    const bResult = getAnswer(arrayB, arrayA)

    return aResult > bResult ? aResult : bResult
}

function getAnswer (A, B) {
    A.sort((a, b) => a - b)
    for (let i = A[0]; i > 1; i--) {
        if (A.every(a => a % i === 0) && !B.some(b => b % i === 0)) return i
    }
    return 0
}

TIL

• array.every(조건) : 배열이 조건에 모두 부합해야 true 반환
  • 시간복잡도 : O(n)
    
    
• array.some(조건) : 배열이 조건에 하나라도 부합하면 true 반환
  • 시간복잡도 : O(n)