코드워즈 - Large Factorials (10/31) (java)

1. 문제

https://www.codewars.com/kata/557f6437bf8dcdd135000010

Codewars: Achieve mastery through challenge

 

문제 설명

n mathematics, the factorial of integer n is written as n!. It is equal to the product of n and every integer preceding it. For example: 5! = 1 x 2 x 3 x 4 x 5 = 120

Your mission is simple: write a function that takes an integer n and returns the value of n!.

You are guaranteed an integer argument. For any values outside the non-negative range, return null, nil or None (return an empty string "" in C and C++). For non-negative numbers a full length number is expected for example, return 25! = "15511210043330985984000000" as a string.

For more on factorials, see http://en.wikipedia.org/wiki/Factorial

NOTES:

• The use of BigInteger or BigNumber functions has been disabled, this requires a complex solution

• I have removed the use of require in the javascript language.

입출력 예

1! 👉 "1"

5! 👉 "120"

9! 👉 "362880"

15! 👉 "1307674368000"

25! 👉 "15511210043330985984000000"

 

---

2. 어떻게 풀까?

 

간단하게 팩토리얼 구하는 함수를 구현해라는 문제인데, NOTE를 보면 BigInteger나 BigNumber를 쓰지 말라고 한다. 이러면 방법을 잘 모르겠다. 처음에는 bit별로 나누어서 list에 저장하고 bit끼리 더하면 되겠다 생각했는데 생각처럼 잘 되지 않았다. 그래서 결국 답을 봤다.

근데 답보니까 다 BigInteger를 썼는데 ㅋㅋ.. 그중에 안쓴 답이 있어서 며칠 동안 다시 풀면서 직접 코드를 짜 봤다.

 

---

3. 코드

 

답을 보고 내가 리팩터링 한 코드

 

테스트 코드

package doNotSolve.codewars.kyu4.largeFactorials_20201029;

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.*;

import org.junit.Test;

public class KataTest {

  @Test
  public void test1() {
    assertThat(Kata.factorial(1), is("1"));
  }

  @Test
  public void test2() {
    assertThat(Kata.factorial(2), is("2"));
  }

  @Test
  public void test3() {
    assertThat(Kata.factorial(5), is("120"));
  }

  @Test
  public void test4() {
    assertThat(Kata.factorial(15), is("1307674368000"));
  }

  @Test
  public void test5() {
    assertThat(Kata.factorial(25), is("15511210043330985984000000"));
  }
}

 

실제 코드

package doNotSolve.codewars.kyu4.largeFactorials_20201029;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

public class KataAgain {

  static int carry;

  public static String factorials(int n) {
    List<Integer> digits = new ArrayList<>();
    int value = n;
    saveDigits(digits, value);

    for (value = n - 1; value > 1; value--) {
      List<Integer> targetDigits = new ArrayList<>();
      carry = 0;
      saveDigits(digits, targetDigits, value);

      saveDigits(targetDigits, carry);
      digits = targetDigits;
    }

    return getResultString(digits);
  }

  private static void saveDigits(List<Integer> digits, List<Integer> targetDigits, int value) {
    for (Integer digit : digits) {
      int product = value * digit + carry;
      targetDigits.add(product % 10);
      carry = product / 10;
    }
  }

  private static void saveDigits(List<Integer> digits, int value) {
    if (value == 0) {
      return;
    }
    while (value > 0) {
      digits.add(value % 10);
      value /= 10;
    }
  }

  private static String getResultString(List<Integer> digits) {
    String reversedDigits = digits.stream().map(String::valueOf).collect(Collectors.joining());
    return new StringBuilder(reversedDigits).reverse().toString();
  }
}

---

4. 느낀 점

memoization 방법으로 팩토리얼을 구현하면 타입을 long으로 해도 20! 에서 오버플로우가 발생한다. 따라서 큰 값의 팩토리얼을 구하려면 BigInteger을 사용해왔는데 새로운 방법을 알게 되었다. 팩토리얼 외에도 피보나치수열도 이 방법으로 할 수 있지 않을까? 생각이 들었다.