[프로그래머스] 숫자 카드 나누기 - 자바스크립트

문제

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

 

코딩테스트 대비 겸 오랜만에 프로그래머스에 들어갔는데, 새로운 문제가 나와서 정리하게 되었다.

 

 

---

코드

function solution(arrayA, arrayB) {
  const cd1 = getCd(...arrayA.slice(0, 2));
  const cd2 = getCd(...arrayB.slice(0, 2));
  const allCdOfArrA = getAllCd(cd1, arrayA);
  const allCdOfArrB = getAllCd(cd2, arrayB);
  const deDuplicatedAllCd = deDuplicate(allCdOfArrA, allCdOfArrB);

  return findAnswer(deDuplicatedAllCd, arrayA, arrayB);
}

function getCd(num1 = 0, num2 = 0) {
  const cd = [];
  const max = Math.max(num1, num2);

  for (let i = 2; i <= max; i++) {
    if (isEqual(num1 % i, 0) && isEqual(num2 % i, 0)) {
      cd.push(i);
    }
  }

  return cd;
}

function getAllCd(cdArr, target) {
  const allCD = [];

  while (cdArr.length) {
    const pop = cdArr.pop();
    let flag = 1;

    for (let i = 0, len = target.length; i < len; i++) {
      if (!isEqual(target[i] % pop, 0)) {
        flag = 0;
        break;
      }
    }

    if (flag) allCD.push(pop);
  }

  return allCD;
}

function deDuplicate(arr1, arr2) {
  return [...new Set([...arr1, ...arr2])].sort((a, b) => b - a);
}

function findAnswer(cd, arr1, arr2) {
  const arr1Len = arr1.length;
  const arr2Len = arr2.length;

  for (let i = 0, len = cd.length; i < len; i++) {
    const cntArr1 = arr1.filter((el) => isCD(el, cd[i])).length;
    const cntArr2 = arr2.filter((el) => isCD(el, cd[i])).length;

    if ((isEqual(cntArr1, arr1Len) && isEqual(cntArr2, 0)) || (isEqual(cntArr2, arr2Len) && isEqual(cntArr1, 0))) {
      return cd[i];
    }
  }

  return 0;
}

function isCD(num, divider) {
  return !(num % divider);
}

function isEqual(a, b) {
  return a === b;
}

---

풀이

문제 조건

철수, 영희는 숫자가 적힌 카드들을 절반씩 나눈다.

다음을 만족하는 가장 큰 양의정수 a의 값을 구한다.

 

1. 철수의 모든 숫자를 나눌 수 있고, 영희가 가진 숫자는 하나도 나눌 수 없는 a

2. 영희의 모든 숫자를 나눌 수 있고, 철수가 가진 숫자는 하나도 나눌 수 없는 a

 

적합한 a가 없다면 0이 정답이다.

 

제한사항

1 <= 숫자카드 array 크기 <= 500,000

1<= 숫자 array 원소 <= 100,000,000

arrayA, arrayB에는 중복된 원소가 있을 수 있다.

 

주어진 숫자카드 배열이 50만개까지 있으므로, 단순한 반복을 해서는 시간초과가 날 수 있다.

전체 배열 반복은 어쩔 수 없는 부분이므로, 반복해야 하는 횟수 자체를 줄여보도록 하는 편이 좋겠다.

 

이에 따라 생각한 방법은 다음과 같다.

 

1. 철수의 모든 숫자의 공약수를 구한다.

2. 영희의 모든 숫자의 공약수를 구한다.

3. 두 공약수 배열을 중복을 없앤 하나의 배열로 만든다.

4. 3번의 배열에서 가장 큰 공약수부터 철수/영희의 모든 숫자를 나누고, 조건1 or 조건2가 만족하면 정답이다.

5. 모든 공약수가 조건1 or 조건2를 만족하지 못한다면 0이 정답이다.

 

***

문제의 조건에 유의한다. 처음 a,b의 공약수를 구할 때,

주어진 숫자카드 배열 원소 갯수가 1개밖에 주어지지 않는다면 b가 undefined일 수도 있다.

***

---

주석을 첨부한 코드

function solution(arrayA, arrayB) {
  const cd1 = getCd(...arrayA.slice(0, 2));
  const cd2 = getCd(...arrayB.slice(0, 2));
  const allCdOfArrA = getAllCd(cd1, arrayA);
  const allCdOfArrB = getAllCd(cd2, arrayB);
  const deDuplicatedAllCd = deDuplicate(allCdOfArrA, allCdOfArrB);

  return findAnswer(deDuplicatedAllCd, arrayA, arrayB);
}

/**
 * getCd 함수는 num1, num2를 받아 공약수의 배열을 반환해준다.
 * array의 원소가 1개일 때는 num2=undefined이므로, 기본값(0 or 1)을 지정해준다.
 */
function getCd(num1 = 0, num2 = 0) {
  const cd = [];
  const max = Math.max(num1, num2);

  for (let i = 2; i <= max; i++) {
    if (isEqual(num1 % i, 0) && isEqual(num2 % i, 0)) {
      cd.push(i);
    }
  }

  return cd;
}

/**
 * getAllCd 함수는 cdArr(공약수배열), target(카드 array)를 받아
 * target 전체의 공약수 배열을 반환한다.
 */
function getAllCd(cdArr, target) {
  const allCD = [];

  while (cdArr.length) {
    const pop = cdArr.pop();
    let flag = 1;

    for (let i = 0, len = target.length; i < len; i++) {
      if (!isEqual(target[i] % pop, 0)) {
        flag = 0;
        break;
      }
    }

    if (flag) allCD.push(pop);
  }

  return allCD;
}

/**
 * deDuplicate 함수는 두개의 배열을 받아 중복을 없앤 뒤 내림차순 정렬한 배열을 반환한다.
 */
function deDuplicate(arr1, arr2) {
  return [...new Set([...arr1, ...arr2])].sort((a, b) => b - a);
}

/**
 * findAnswer 함수는 공약수배열, arrayA, arrayB를 받아
 * 가장 큰 공약수부터 조회하면서 조건1 or 조건2를 만족한다면 정답으로 반환해준다.
 * 모든 공약수가 조건을 만족하지 못한다면, 0을 반환한다.
 */
function findAnswer(cd, arr1, arr2) {
  const arr1Len = arr1.length;
  const arr2Len = arr2.length;

  for (let i = 0, len = cd.length; i < len; i++) {
    const cntArr1 = arr1.filter((el) => isCD(el, cd[i])).length;
    const cntArr2 = arr2.filter((el) => isCD(el, cd[i])).length;

    if ((isEqual(cntArr1, arr1Len) && isEqual(cntArr2, 0)) || (isEqual(cntArr2, arr2Len) && isEqual(cntArr1, 0))) {
      return cd[i];
    }
  }

  return 0;
}

function isCD(num, divider) {
  return !(num % divider);
}

function isEqual(a, b) {
  return a === b;
}

당연히, 더 효율적인 방법이 있을 수 있다. 

"이렇게도 푸는구나."정도로만 참고해주시길 바랍니다!.