[프로그래머스] 레벨 0 - 분수의 덧셈

Hoon Kang·2022년 11월 15일

프로그래머스

목록 보기

1/3

문제 설명

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

제한사항
0 < numer1, denom1, numer2, denom2 < 1,000

첫 시도

문제를 처음 봤을때는 '레벨0 문젠데 너무 어려운 거 아냐?'라는 생각이 들었다. 그래도 하루에 프로그래머스에서 추천하는 4문제씩은 꼭 풀자고 마음먹었고, 그래서 여러번의 시행착오 끝에 정답을 맞췄다.
(그리고, 사실 전혀 어려운 문제가 아니었다.)

코드

function solution(denum1, num1, denum2, num2) {
  let fraction1 = [denum1, num1];
  let fraction2 = [denum2, num2];
  let lcm = 1;

  while (true) {
    if (lcm % num1 === 0 && lcm % num2 === 0) {
      break;
    }
    lcm++;
  }

  if (num1 > num2) {
    fraction2[0] = Math.floor(lcm / num2) * denum2;
    fraction1[0] = Math.floor(lcm / num1) * denum1;
    fraction2[1] = lcm;
  } else if (num1 < num2) {
    fraction1[0] = Math.floor(lcm / num1) * denum1;
    fraction2[0] = Math.floor(lcm / num2) * denum2;
    fraction1[1] = lcm;
  } else {
    fraction1 = [denum1, num1];
    fraction2 = [denum2, num2];
  }

  const sumNum = lcm;
  const sumDenum = fraction1[0] + fraction2[0];

  let gcd = 1;

  for (let i = 2; i <= Math.min(sumNum, sumDenum); i++) {
    if (sumNum % i === 0 && sumDenum % i === 0) {
      gcd = i;
    }
  }
  let answer = [Math.floor(sumDenum / gcd), Math.floor(sumNum / gcd)];

  console.log(answer);
  return answer;
}

...이게 뭐고...

문제는 풀었지만, 작성한 내가 봐도 "일단 돌아는 갑니다." 수준의 코드였고, 가독성도 매우 떨어졌기에 조금 더 생각을 해 보기로 했다. 처음 코드를 작성했을 때 내가 생각했던 알고리즘은 다음과 같았다:

주어진 입력값을 바탕으로 두 개의 분수 배열을 생성한다.
통분을 위해 두 분수의 최소공배수를 구한다.
구한 최소공배수를 통해 두 분수를 통분한다.
(불필요하게 통분하는것을 줄이기 위해서 각 분모의 크기를 비교해, 통분이 필요한 분수에만 곱해준다!)
그렇게 통분한 분수들을 서로 더해서 새로운 통분된 분수의 배열에 저장해 준다.
그 배열에 저장된 분수와 분모를 최대공약수로 나누어 기약분수로 만들어 준다!

...그리고 내 알고리즘이 매우 복잡하고 지저분하다는 사실을 깨닫는 데에는 대략 한 시간 정도가 걸렸다.

다시 생각해 봅시다

두 분수의 통분

일단 두 분수의 최소공배수를 구해 조건문을 통해서 통분을 한다는 것 자체가 매우 비효율적인 일이었다. 사실 더 빠르고 깔끔한 계산법을 나는 알고 있었다. 두 분수를 통으로 통분해버리면 될 일 아닌가! 인자로 주어진 두 분수를 그대로 통분해서 더한 다음 하나의 배열을 만드는 것이 더 간단했고, 불필요한 코드를 줄일 수 있었다.

const commonDenomFraction = [(number1 * denom2) + (number2 * denom1), denom1 * denom2];

이렇게 받아온 인자를 다른 배열에 저장하지 않고 그대로 계산해서 하나의 통분 배열에 집어넣으면, 1, 2, 3, 4번의 과정을 하나로 줄일 수 있다.

최대공약수와 유클리드 알고리즘

최대공약수 구하기

그렇다면 통분된 분수 commonDenomFraction의 최대공약수는 어떻게 구해야 할까? 최대공약수는 두 수의 공약수들 중 가장 큰 수이다. 그렇기 때문에 나는 최대공약수를 1부터 하나씩 늘려가며 분모 sumNum과 분자 sumDenum를 나누어보고, 둘 중 하나라도 나누어지지 않을 때 바로 직전의 수가 최대공약수가 되도록 하는 코드를 작성했다.

let gcd = 1;

for (let i = 2; i <= Math.min(sumNum, sumDenum); i++) {
  if (sumNum % i === 0 && sumDenum % i === 0) {
    gcd = i;
  }
}

이렇게만 구해도 코드는 예전보다 훨씬 더 깔끔해지지만, 그래도 조금은 더 깔끔하게 구할 수 있는 방법은 없을까 고민하다가 유클리드 알고리즘을 발견하게 되었다.

유클리드 알고리즘

유클리드 호제법 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 이는 명시적으로 기술된 가장 오래된 알고리즘으로서도 알려져 있으며, 기원전 300년경에 쓰인 《원론》 제7권, 명제 1부터 3까지에 해당한다.

핵심만 풀어서 조금 더 간단하게 설명하자면, 어떤 두 수 A, B에 대해서 A를 B로 나눈 나머지를 r이라 하고, A, B의 최대공약수를 gcd(A, B), B와 r의 최대공약수를 gcd(B, r)이라고 한다면, 그 두 개의 최대공약수는 서로 같고, 해당 과정을 반복해서 나머지가 0이 될 때 나누는 수가 A와 B의 최대공약수가 된다는 것이다.
명시적으로 기술된 가장 오래된 알고리즘이라니, 매력적이지 않은가! 너무나도 매력적이어서 한번 사용해 보고 싶었고, 바로 적용시켜보았다.

const euclidean = (num1, num2) => {
  if (num1 % num2 === 0) {
    return num2;
  }
  return euclidean(num2, num1%num2);
}

euclidean() 에서 반환된 값이 바로 최대공약수였고, 이 최대 공약수로 통분 배열의 분모와 분자를 나눠 주면 정답을 구할 수 있었다. 그런데 여기까지 코드를 작성하다 아차 싶은 생각이 들었다. 분명 유클리드 알고리즘의 정의에 따르면, (a > b)일 때만 해당 알고리즘이 적용된다는 것이었다. 그렇다면 만약 통분된 배열의 분모가 분자보다 크다면 오류가 발생하는 것이 아닐까? 라는 생각을 했지만, 다행히 그렇지 않았다.

예를 들어, 통분 분수의 배열이 [3, 12]와 같다고 하자. 이 경우, euclidean(3, 12)함수 내부의 과정에서 나머지는 자연스럽게 3이 된다. 그렇게 되면 재귀 과정에서 euclidean(12, 3)을 불러오게 된다. 즉, 재귀 과정에서 자연스럽게 큰 값이 앞으로, 작은 값이 뒤로 들어가게 된다.

휴, 이제 좀 살겠네

그렇게 더 나은 방법을 찾으려고 한 결과, 내 코드는 훨씬 더 깔끔해졌다.

const solution = (number1, denom1, number2, denom2) => {
  let commonDenomFraction = [(number1 * denom2) + (number2 * denom1), denom1 * denom2];
  let gcd = euclidean(commonDenomFraction[0], commonDenomFraction[1]);
  let answer = [commonDenomFraction[0]/gcd, commonDenomFraction[1]/gcd];
  return answer;
}

const euclidean = (num1, num2) => {
  if (num1 % num2 === 0) {
    return num2;
  }
  return euclidean(num2, num1%num2);
}