프로그래머스 구슬을 나누는 경우의 수 <7점> - 자바(java) 조합 Biginteger

 

 

확통은 자신있었는데

 

 

 

먼저 문제를 보자마자 공식에서 변형시켜서 적용해야겠다~ 라는 생각이 있었다.

조합은 아래 공식이 맞지만. 조금 수정하면 편하게 사용이 가능했다.

 

예시로 5C3을 계산하면 5*4*3*2*1 / 2*1*3*2*1 인데 이는 5*4 / 2*1  과 동일하다.

또한 5C2 와 5C3이 동일하다. 5*4/2*1 은 5*4*3/3*2*1 은 같기 때문이다.

이를 고민하면 간단하겠다~ 라고 생각했다.

 

class Solution {
    public long solution(int c, int n) {
        long answer = 0;
        int a = 0;
        if (c-n < n){
            a = c-n;
        }else a = n;
        
        int top = 1;
        int bot = 1;
        
        
        for(int i = 0; i < a; i++){
            top *= c;
            c--;
        }
        for(int j = 0; j < a; j++){
            bot *= a;
            a--;
        }
        answer= top/bot;
        return answer;
 
    }
}

 

초기 코드이다.

먼저 5C2와 5C3처럼 n의 숫자를 보다 작은걸 선택하기 위해서

    if (c-n < n){
    a = c-n;
    }else a = n;

를 작성했다.

 

        for(int i = 0; i < a; i++){
            top *= c;
            c--;
        }
        for(int j = 0; j < a; j++){
            bot *= a;
            a--;
        }
        answer= top/bot;

 

이후 분자와 분모를 나누어 반복문을 통해 팩토리얼을 간소화하여 구했고, 테스트는 가볍게 통과했다.

그러나 숫자가 커지는 30C12 이런경우 overflow 때문인지 모두 통과하지 못했다.

아오아오아오

그러면 분자와 분모를 한 사이클에서 해결해야 겠다고 생각했다.

한 사이클 돌때마다 나누어 버리면 숫자가 작아지니 말이다.

 

        for (int i = 0; i < a; i++) {
            answer *= (c - i);
            answer /= (i + 1);
        }

 

팩토리얼을 재귀함수를 많이 활용하나 처음 생각한 방식대로 작성을 해 보았다.

 

class Solution {
    public long solution(int c, int n) {
        if (c == n || n == 0)
            return 1;
 
        long answer = 1;
        int a = (c - n < n) ? c - n : n;
 
        for (int i = 0; i < a; i++) {
            answer *= (c - i);
            answer /= (i + 1);
        }
 
        return answer;
    }
}
 

 

최종코코드드.. 이렇게 쉬운걸.. 가독성을 높이려 삼항연산자를 쓰니 더 쉬워졌다.

 

맹해서 운동다녀오고 나니까 풀려서 다행이다. 2시간 넘게 걸린 문제였다..

 

import java.math.BigInteger;
class Solution {
    public int solution(int balls, int share) {
        int answer = 0;
 
        BigInteger bN[] = new BigInteger[balls+1];
 
        bN[0]= new BigInteger("1");
        for(int i=1;i<=balls;i++) {
 
                bN[i] = new BigInteger(Integer.toString(i));
                bN[i] = bN[i].multiply(bN[i-1]);
        }
 
        answer=bN[balls].divide(bN[share].multiply(bN[balls-share])).intValue();
 
         return answer;
    }
 
}

다른분의 코드인데 BigInteger를 활용해서 푸는 경우가 대부분이었다.

 

• 정리

Int형의 경우 32비트 고정크기이므로 약 -2^32 ~ 2^32 범위를 가진다. 이는 20억정도이다.

long형의 경우 64비트로 -2^64 ~ 2^64 범위이다. 이는 9경정도로 메모리는 당연히 int보다 많이 소모한다.

마지막으로 BigInteger은 사용 가능한 메모리에 의해서만 제한되는 모든 크기의 정수를 처리할 수 있다.

매우 큰 정수에 대한 계산을 수행해야 하거나 결과의 정확한 정밀도가 중요한 경우에 사용된다.

운동도 안되고~ 이건 뭐