구슬을 나누는 경우의 수

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

프로그래머스

 

팩토리얼!

 

내가 처음에 제출했던 코드를 보자.

class Solution {
    public int solution(int balls, int share) {
        // balls! / ((balls-share)! * share!)
        return factorial(balls) / (factorial(balls-share) * factorial(share));
    }
    
    int factorial(int n) {
        if(n>=2) {
            return n * factorial(n-1);
        }
        return 1;
    }
}

 

코드 상으로는 문제 될 게 없다고 생각했는데 정확도가 42.9/100...

이 건에 대해서는 도저히 알 수가 없어서 GPT한테 물었다.

일단 문제가 될 수 있는 건 '오버플로우'.

그래서 아래처럼 수정했더니 아무 오류도 나지 않았다.

import java.math.BigInteger;

class Solution {
    public int solution(int balls, int share) {
        // balls! / ((balls-share)! * share!)
        BigInteger result = factorial(balls)
            .divide(factorial(balls-share)
            .multiply(factorial(share)));
        return result.intValue();
    }
    
    BigInteger factorial(int n) {
        BigInteger result = BigInteger.ONE;
        for(int i=2; i<=n; i++) {
            result = result.multiply(BigInteger.valueOf(i));
        }
        return result;
    }
}

 

리턴값이나 변수에 다 BigInteger를 적용했다.

팩토리얼 함수는 그냥 for문 돌리는 걸로 고쳤다.

 

오버플로우 날 확률을 줄이기 위해 식을 나눗셈을 먼저 하는 걸로 진행해야 하느냐 곱셈을 먼저 하는 걸로 진행해야 하느냐 GPT한테 물었는데

그때 그때마다 뱉는 답변이 다르다.

우선, / / 하나 * 먼저 하고 / 하나 속도에는 별 차이가 없다.

그 외 내부적으로는 어딘가에서 중간 결과가 데이터 타입의 범위를 초과하는 일이 생기겠지만

내가 그 지점까지는 그릴 수가 없어서...

그래서 우선은 팩토리얼 할 때 오버플로우 조심하자 정도가 이번 문제에서 얻은 교훈이 되겠다.

그리고 빅인티저 잘 쓰자.

 

주의할 것:

1. 정수 오버플로우: int 형으로 팩토리얼 값을 계산하면 빠르게 정수 범위를 초과할 수 있습니다. 예를 들어, 13! 이상부터는 int 범위를 넘어서며, long 타입을 사용해도 20! 이상에서는 범위를 초과합니다.
2. 해결: 팩토리얼을 계산하는 부분을 BigInteger를 사용하여 다시 작성할 수 있습니다. BigInteger는 아주 큰 정수를 다룰 수 있는 클래스로, 사실상 무제한의 크기를 지원합니다.

이런 문제에서는 걍 애초부터 맘 편하게 빅인티저 쓸 것.