분수의_덧셈.md

분수의 덧셈

프로그래머스

문제

첫 번째 분수의 분자와 분모를 뜻하는 numer1, denom1, 두 번째 분수의 분자와 분모를 뜻하는 numer2, denom2가 매개변수로 주어집니다. 두 분수를 더한 값을 기약 분수로 나타냈을 때 분자와 분모를 순서대로 담은 배열을 return 하도록 solution 함수를 완성해보세요.

제한사항

0 < numer1, denom1, numer2, denom2 < 1,000

첫 번째 제출 코드

function solution(numer1, denom1, numer2, denom2) {
  const getFactors = (num) => {
    const factors = [];
    let devidedNumber = num;
    let i = 2;
    while (i < num) {
      if (devidedNumber % i === 0) {
        factors.push(i);
        devidedNumber = devidedNumber / i;
        continue;
      }
      i++;
    }
    return factors;
  };

  const newNumer = numer2 * denom1 + numer1 * denom2;
  const newDenom = denom1 * denom2;
  const numerFactors = getFactors(newNumer);
  const denomFactors = getFactors(newDenom);
  const temp = [];
  numerFactors.forEach((factor) => {
    const index = denomFactors.indexOf(factor);
    if (index === -1) {
      temp.push(factor);
      return;
    }
    denomFactors.splice(index, 1);
  });
  if (temp.length === 0) return [1, 1];
  const irreducibleNumer = temp.reduce((acc, curr) => acc * curr);
  const irreducibleDenom = denomFactors.reduce((acc, curr) => acc * curr);
  return [irreducibleNumer, irreducibleDenom];
}

풀이 과정

• 문제를 푸는 기본 논리는 다음과 같다.

1. 두 분수의 분모를 단순히 곱해 분수의 덧셈을 수행한다.
2. 분모와 분자 모두에 대해 소인수분해를 하고, 인수의 배열을 만든다.
3. 분자의 배열을 순회하며 인수를 검사한다.

• 만약 분모의 인수 배열에 포함되어 있다면 분모의 배열에서 해당 요소를 삭제한다.
• 만약 분모의 인수 배열에 없다면 해당 인수를 임시 배열에 넣는다.

4. 만약 임시 배열의 length 속성값이 0이라면 분모와 분자가 같은 수라고 가정하고 [1, 1]을 반환한다.
5. 아니라면 분모의 인수 배열과 분자의 인수 배열에 리듀서 함수를 적용하여 모든 인수를 곱한 값을 구한다.
6. 마지막으로 앞에서 구한 두 값을 배열에 담아 반환한다.

문제점

첫 번째 풀이에는 두 가지 문제가 있다.

1. 분수의 덧셈으로 만들어진 분모와 분자가 처음부터 기약분수일 경우 틀린 답이 나온다.
2. 분모나 분자 중 하나가 다른 하나의 인수인 경우 틀린 답이 나온다.

두 번째 풀이

function solution(numer1, denom1, numer2, denom2) {
  let newNumer = numer2 * denom1 + numer1 * denom2;
  let newDenom = denom1 * denom2;
  if (newNumer === newDenom) return [1, 1];
  const minimum = newNumer > newDenom ? newDenom : newNumer;
  let i = 2;
  while (i <= minimum) {
    if (newNumer % i === 0 && newDenom % i === 0) {
      newNumer = newNumer / i;
      newDenom = newDenom / i;
      continue;
    }
    i++;
  }
  return [newNumer, newDenom];
}

풀이 과정

1. 두 분수의 덧셈으로 분수와 분모를 얻는 것까지는 첫 번째 풀이와 같다.
2. 만약 분자와 분모가 같다면 이 시점에서 먼저 [1, 1]을 반환한다.
3. 이후 분자와 분모 중 더 작은 값을 minimum으로 선정한다.
4. 2부터 minimum까지 1씩 증가시키며 분모와 분자를 나눠본다.

• 만약 두 수를 모두 나누어 떨어지게 할 수 있다면 나눠진 분모와 분자 값을 새로운 분모 분자로 사용한다.
• 아니라면 나누는 수에 1을 더한다.

5. 이 과정이 끝나면 마지막으로 구해진 분모와 분자를 배열에 담아 반환한다.

알고 가자

• 자바스크립트 배열에서 특정 인덱스 아이템을 삭제하고자 하는 경우 splice 메소드의 deleteCount 매개변수를 활용할 수 있다.