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

문제 출처

프로그래머스 lev2 - 숫자 카드 나누기

나의 풀이

1차시도(77.8/100)

단순히 최대공약수를 구하는게 아니라
약수들을 전부 구해서 배열 형태로 전부 구했다.

약수로 구성된 배열을 순회하면서, 상대방 쪽에서 약수에 해당이 안 되는 녀석이 정답 후보가 된다.

이들을 정답 배열에 넣은 뒤, 정답 배열 중 최대값을 반환한다.

하지만 시간초과가 발생한다...

const division = (array, target) => {
  let possible = []

  for(let i=0; i<array.length; i++){
    let tmp = []
    
    for(let j=2; j<=Math.sqrt(array[i]); j++){
      if(array[i] % j === 0){
        tmp.push(j)
        // 약수를 구할 때 제곱근으로 하면 제곱근 넘어가는 약수를 못 구하므로 아래 코드가 추가되어야 한다. 
        if(j != array[i] / j) tmp.push(array[i] / j);
      }
    }
    tmp.sort((a, b) => b - a)
    possible.push([array[i], ...tmp])
  }

  for(let i=1; i<possible.length; i++){
    // 배열 간 교차 비교를 통해 공통 원소만 추출하는 방법이다. 
    possible[i] = possible[i].filter(x => possible[i-1].includes(x))
  }

  if(possible[possible.length-1].length === 0) return []

  let result = []
  for(let k=0; k<possible[possible.length-1].length; k++){

    let flag = true 
    for(let l=0; l<target.length; l++){

      if(target[l] % possible[possible.length-1][k] === 0){
        flag = false
        break
      } 
      if(!flag) break
    }


    if(flag){
      result.push(possible[possible.length-1][k])
      break
    }
  }

  return result 
}

function solution(arrayA, arrayB) {
  const res = [...division(arrayA, arrayB), ...division(arrayB, arrayA)]
  if(res.length === 0) return 0
  return Math.max(...res)
}

console.log(solution([10, 17], [5, 20]))
console.log(solution([10, 20], [5, 17]))
console.log(solution([14, 35, 119], [18, 30, 102]))

2차시도(통과)

모든 공약수를 구하지 않고 최대공약수만 구했다.

문제의 질문이
A그룹(또는 B그룹)에서의 약수가 B그룹(또는 A그룹)에서는 약수가 되지 않는 수 중에서 최대값이므로,
어차피 한쪽에서는 약수가 되고 다른 한쪽에서는 약수가 되지 않는 조건을 만족하는 약수 중 최대이려면 최대공약수일 수밖에 없다.

const gcd = (a, b) => {
  if(b === 0) return a;
  return gcd(b, a % b);
}

const division = (array, target) => {
  let value = array[0]

  for(let i=1; i<array.length; i++) {
    value = gcd(value, array[i])
  }

  if(value === 1) return 0

  let flag = true 
  for(let i=0; i<target.length; i++){
    if(target[i] % value === 0){
      flag = false
      break
    }
    if(!flag) break
  }
  if(flag) return value
  return 0
}

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

다른 풀이

n개의 공약수가 되려면, n개 중에서 가장 작은 값보다 클 수가 없다.

sort로 배열을 정렬한 뒤, 배열[0] 부터 시작해서 하나씩 값을 빼가면서 약수를 구한다.

그 약수에 대해서,
A에서는 every를 통해서, A의 모든 요소의 약수 조건이 되고
A.every(a => a % i === 0)
B에서는 some을 통해서, B의 요소 중 하나라도 약수가 되지 않을 때만
그 약수를 구해서 반환한다.
!B.some(b => b % i === 0)

없으면 0을 반환한다.

i--를 통해 역순으로 for순회하므로 최대값으로 구할 수 있다.

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
}

약간의 개념정리

1. 모든 약수 빠르게 구하기

제곱근까지만 for 순회하면 모든 약수를 구할 수 없으므로
if 조건으로 한번에 같이 구해준다.

j === array[i]/j인 경우는
3*3 = 9 처럼 중복값이므로 이를 제외하고 구해주면 된다.

for(let j=2; j<=Math.sqrt(array[i]); j++){
  if(array[i] % j === 0){
    tmp.push(j)
    // 약수를 구할 때 제곱근으로 하면 제곱근 넘어가는 약수를 못 구하므로 아래 코드가 추가되어야 한다. 
    if(j != array[i] / j) tmp.push(array[i] / j);
  }
}

2. 배열 간 공통 원소

아래와 같이 filter와 includes를 활용하되,
배열 2개 이상을 비교할 경우, for문으로 비교하면
가장 마지막 배열에 공통 원소만 남게 된다.

for(let i=1; i<possible.length; i++){
  // 배열 간 교차 비교를 통해 공통 원소만 추출하는 방법이다. 
  possible[i] = possible[i].filter(x => possible[i-1].includes(x))
}

3. n개의 공약수

0으로 나눠떨어지는 시점이 최대공약수이다.
for 순회를 하면 n개의 공약수를 구할 수 있다.

const gcd = (a, b) => {
  if(b === 0) return a;
  return gcd(b, a % b);
}

for(let i=1; i<array.length; i++) {
  value = gcd(value, array[i])
}