[프로그래머스 120840] Java - 코딩테스트 입문 / 구슬을 나누는 경우의 수

 

 

구슬을 나누는 경우의 수

 

 

 

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

프로그래머스

 

 

 

1)  문제

머쓱이는 구슬을 친구들에게 나누어주려고 합니다. 
구슬은 모두 다르게 생겼습니다. 
머쓱이가 갖고 있는 구슬의 개수 balls와 친구들에게 나누어 줄 구슬 개수 share이 매개변수로 주어질 때, balls개의 구슬 중 share개의 구슬을 고르는 가능한 모든 경우의 수를 return 하는 solution 함수를 완성해주세요.

제한사항
1 ≤ balls ≤ 30
1 ≤ share ≤ 30
구슬을 고르는 순서는 고려하지 않습니다.
share ≤ balls

 

 

 

 

2)  예시

 

 

balls	share	result
3	2	3
5	3	10

 

 

 

입출력 예 #1
서로 다른 구슬 3개 중 2개를 고르는 경우의 수는 3입니다.

입출력 예 #2
서로 다른 구슬 5개 중 3개를 고르는 경우의 수는 10입니다.

 

 

 

 

 

 

 

 

 

3)  풀이

 

 

0. BigInteger 클래스를 사용하기위해 BigInteger 클래스를 import해줍니다.

이 문제에서 balls와 share는 30이하의 수라고 합니다.

만약 30이 되게 된다면 아래 4번 설명에 있는 팩토리얼을 시행하게되면, 30!의 경우 int 및 long이 표현할 수 있는 최대값을 초과해버리고 오버플로우 오류가 발생하기 때문에 BigInteger를 이용해줍니다.

● import java.math.BigInteger;

 

 

※ BigInteger 란?

정수형 데이터를 다루고 표현하는 클래스로 java.math 패키지 안에 속해있으며, int나 long으로 표현이 불가능한 매우 큰 정수를 표현할 수 있습니다.

BigInteger 클래스는 불변(immutable) 객체로, 한 번 생성된 BigInteger 객체는 변경할 수 없습니다. 

따라서 BigInteger 객체에 수학 연산을 수행하면 새로운 BigInteger 객체가 생성되어 반환됩니다.

 

※ 정수의 최대 표현값

• int: 32비트를 사용하여 정수를 표현합니다. 최대 표현값은 2^31 - 1입니다. 즉, Integer.MAX_VALUE는 2,147,483,647입니다.
• long: 64비트를 사용하여 정수를 표현합니다. 최대 표현값은 2^63 - 1입니다. 즉, Long.MAX_VALUE는 9,223,372,036,854,775,807입니다.
• BigInteger: BigInteger 클래스는 정수의 크기에 제한이 없으므로 사용 가능한 메모리에 따라서 최대값이 결정됩니다.

 

 

 

 

 

1. 클래스 선언을 해줍니다

● class Solution {

클래스명은 대문자로 시작해야하고, 정답이라는 의미로 Solution이라는 단어를 사용하였습니다.

 

 

 

 

2. 정수 balls와 share를 매개변수로 하는 solution 메소드를 선언합니다.

solution은 정수를 반환하므로 데이터타입을 int으로 합니다.

●   public int solution(int balls, int share) {

 

 

 

 

3. 제한사항을 검사합니다. 제한사항을 만족하지 않을 경우, 예외처리합니다.

●     if (balls < 1 || balls > 30 || share < 1 || share > 30 || share > balls) {
            throw new IllegalArgumentException("제한사항을 확인하세요");
        }

 

 

 

 

 

4. 우선 팩토리얼(n!)에 대해 알아봅시다.

팩토리얼 n!은 n, n-1, n-2, · · ·, 1까지의 수를 모두 곱한 값을 의미합니다.

문제에서 서로 다른 n개의 m개를 뽑는 공식상 팩토리얼이 있으므로, 이를 구현하기 위한 메소드를 먼저 만들어줍니다.

 

BigInteger 클래스를 사용하여 n의 팩토리얼을 계산하는 메서드를 정의해줍니다.

BigInteger result는 1로 초기화해줍니다.
(원래는 valueOf(n)메소드로 특정값을 부여하지만,

1의 값을 주는 것은 .ONE 메소드로 정의되어있어 더욱 편리하게 사용할 수 있습니다.)

 

그리고 for문을 사용하여 1부터 n까지 1씩 더해주며 순환하여, 모두 곱해주는 값을 BigInteger result 값이 되게합니다.

BigInteger 클래스는 사칙연산 기호를 사용하지 않고, add, subtract, multiply, divide를 사용합니다.

●     private BigInteger factorial(int n) {
        BigInteger result = BigInteger.ONE;
        for (int i = 1; i <= n; i++) {
            result = result.multiply(BigInteger.valueOf(i));
        }

 

 

 

 

 

 

 

 

 

결국 이 문제에서 적용시켜야할 공식

 

 

 

5. 분자 계산을 해줍니다.

● BigInteger numerator = factorial(balls);

 

 

 

 

6. 분자 계산을 해줍니다.

● BigInteger denominator = factorial(balls - share).multiply(factorial(share));

 

 

 

 

7. 분자 / 분모를 해주어 위 공식과 같은 형태가 되게합니다.

그리고 나누어준 값을 intValue()메소드를 이용해서 BigInteger값을 Int값으로 반환합니다.

이렇게 되면 solution 메소드는 int 값을 반환하도록 되어있으니 일치하게 됩니다.

● return numerator.divide(denominator).intValue();

 

 

 

 

 

 

 

4)  코드

 

import java.math.BigInteger;

class Solution {
    public int solution(int balls, int share) {
        if (balls < 1 || balls > 30 || share < 1 || share > 30 || share > balls) {
            throw new IllegalArgumentException("제한사항을 확인하세요");
        }

        BigInteger numerator = factorial(balls);
        
        BigInteger denominator = factorial(balls - share).multiply(factorial(share));

        return numerator.divide(denominator).intValue();
    }
    
    private BigInteger factorial(int n) {
        BigInteger result = BigInteger.ONE;
        for (int i = 1; i <= n; i++) {
            result = result.multiply(BigInteger.valueOf(i));
        }
        return result;
    }
}

 

 

\

 

 

 

 

5)  느낀점

 

class Solution {
    public int solution(int balls, int share) {
        if (balls < 1 || balls > 30 || share < 1 || share > 30 || share > balls) {
            throw new IllegalArgumentException("제한사항을 확인하세요");
        }

        // 분자 계산
        int numerator = balls * (balls - 1);
        
        // 분모 계산
        int fwdDenominator = (balls - share) * (balls - share -1);
        int aftDenominator = share * (share -1);
        int denominator = fwdDenominator * aftDenominator;

        return numerator / denominator;
    }
}

 

위 코드가 제일 처음 내가 문제를 풀어냈을 때 작성한 코드입니다.

이 때 팩토리얼에 대한 개념 자체가 잘못되어있었습니다.

n -> 1까지 쭉 곱해줘야하는 것인데, n * (n-1)을 해주는 것이 팩토리얼이라고 잘못 생각하고 문제를 풀었습니다.

그런데 또 희한하게 테스트결과 40% 정도의 정답을 보였습니다.... 음?!??

하지만 일단 틀린 것은 틀린 것이니!!

2시간 동안 머리를 싸맸으나, 실패하였고 결국 다른 사람의 코드를 참조하기로 결정하였습니다. 하지만 이게 왠일...

팩토리얼에 대해 잘못 알고있었으니 당연히 머리 싸매도 답이 안나오죠 ㅠㅠㅠㅠ

 

 

 

 

class Solution {
    public int solution(int balls, int share) {
        if (balls < 1 || balls > 30 || share < 1 || share > 30 || share > balls) {
            throw new IllegalArgumentException("제한사항을 확인하세요");
        }

        int numerator = factorial(balls);
        
        int denominator = factorial(balls - share) * factorial(share);

        return numerator / denominator;
    }
    
    private int factorial(int n) {
        int result = 1;
        for (int i = 1; i <= n; i++) {
            result *= i;
        }
        return result;
    }
}

 

이건 이제 팩토리얼 개념에 대해 알아서 작성한 코드입니다.

하지만...! 여전히 오류가 발생하였습니다.

그 이유는 바로 30!의 경우 int로도, long으로도 표현할 수 없는 큰 정수이기 때문입니다.

그래서 BigInteger클래스를 사용해야한다는 사실을 인지하고, 그에 대해 공부할 수 있는 좋은 기회였습니다.

이게 level0이 맞나 흑흑....ㅠㅠ 아니 맞죠 그러니 공부가 되는거겠죠