기록하는 공부
[Programmers] 120840 구슬을 나누는 경우의 수 (BigInteger 사용 / 간단 코드 작성 / 덧셈과 나눗셈을 동시에 / for문 변수 2개 / 재귀 함수 사용 / 팩토리얼 / 콤비네이션 계산) 본문
[Programmers] 120840 구슬을 나누는 경우의 수 (BigInteger 사용 / 간단 코드 작성 / 덧셈과 나눗셈을 동시에 / for문 변수 2개 / 재귀 함수 사용 / 팩토리얼 / 콤비네이션 계산)
SS_StudySteadily 2023. 7. 20. 16:42
문제 출처
https://school.programmers.co.kr/learn/courses/30/lessons/120840
와... 머리로는 이해가 갔지만 계속 테스트 케이스에서 오류가 발생해서 머리가 아팠던 문제...
해결하고 나니 너무 간단하고 쉬워서 아쉬웠다 ㅠㅠ
이 문제를 풀면서 BigInteger라는 것도 알 수 있었고 유익했던 풀이 시간이었다.
그럼 문제 풀이로 고고 !
문제 풀이 1 (for문 속에 변수 2개)
class Solution {
public int solution(int balls, int share) {
long answer = 1;
for(long i=0, j=1; i<share; i++) {
answer *= balls;
balls--;
answer /= j;
j++;
}
return (int)answer;
}
}
파이썬에서는 for문에 변수 2개를 사용할 수 있다는 것을 알고 있었다.
자바에서도 이 방법이 적용되는지 찾아본 결과 가능하다는 것을 알게 되었다.
처음에는 up 변수와 down 변수를 생성해 분자와 분모 값을 따로 계산한 후 answer에 대입할 때 두 값을 나누려고 했는데
자료형의 크기가 맞지 않아 계속 성공하지 못하였다.
(찾아보니 long 형으로도 자료형 크기가 커버가 안돼서 BigInteger를 사용한다고 한다.
문제 풀이 3에서 해결해 볼 예정 !)
코드에 대해 설명하자면,
for문에서 변수 i는 nCm에서 n을 m만큼 카운팅 하는 변수로 사용했다.
변수 j는 1부터 m까지 곱하기 위한 변수로 사용했다.
예를 들어, 5C3을 계산하는 경우를 생각해 보자.
분자는 5 x 4 x 3,
분모는 3 x 2 x 1 이므로
먼저, answer에 share만큼 곱한다.
balls x (balls - 1) x (balls - 2) => 5 x 4 x 3
그리고, 동시에 answer에서 share만큼의 값을 나눠준다.
1 x (share + 1) x (share + 2) => 1 x 2 x 3
그래서 곱셈과 나눗셈을 for 문 안에서 동시에 계산하기 때문에
BigInteger를 사용하지 않고 long 만 사용해도 문제를 해결할 수 있었다.
문제 풀이 2 (재귀함수 사용)
class Solution {
public int solution(int balls, int share) {
return combination(balls, share);
}
public static int combination(int n, int m) {
if (n == m || m == 0) {
return 1;
} else
return combination((n-1), (m-1)) + combination(n-1, m);
}
}
combination이라는 재귀 함수를 사용해 문제를 해결해 보았다.
combination에 balls와 share을 매개변수로 넣는다.
만약, balls와 share가 같거나 share가 0이라면 값이 1이기 때문에 1을 리턴한다.
아닌 경우에는 다시 combination 함수를 호출하여 계산을 반복한다.
수학에 약해서 이론으로는 이해 가는데 코드로 짜려니까 혼란스러워서 직접 써보면서 이해했다.
예시로 5C3을 생각해 보자.
코드에 대입했을 경우에는 balls가 5, share는 3이다.
이 값은 combination 함수로 들어가 if문 조건을 비교하고 일치하지 않기 때문에 else 문으로 내려온다.
그리고 다시 4C2 + 4C3으로 반환된다.
4C2과 4C3은 각각 다시 combination 함수로 들어가 계산된다.
4C2 역시 if문의 조건과 일치하지 않기 때문에 else문으로 내려오고 3C1 + 3C2로 반환된다.
4C3 도 똑같이 else문으로 내려와 3C2 + 3C3으로 반환된다.
4C2의 반환값인 3C1 + 3C2를 살펴보자.
3C1은 if문 조건에 맞지 않아 else문으로 내려와 2C0 + 2C1을 반환한다.
3C2는 역시 if문에 조건에 맞지 않아 2C1 + 2C2를 반환한다.
3C1의 반환값인 2C0 + 2C1을 보면 2C0은 m값이 0이기 때문에 if문의 조건을 만족해 1을 반환하고
2C1은 다시 combination 함수로 들어가 1C0 + 1C1을 반환하고
이 값들은 다시 combination 함수로 들어가 각각 1씩 반환된다.
3C2의 반환값인 2C1 + 2C2를 보면 2C2는 if문에 n==m을 성립시키기 때문에 1을 반환하고
2C1은 combination 함수로 들어가 1C0 + 1C1을 반환하고
이 값들은 다시 combination 함수로 들어가 각각 1씩 반환된다.
4C3의 역시 위와 같은 원리로 진행되는 것을 아래 수식을 직접 써보면서 이해할 수 있었다.
문제 풀이 3 (BigInteger 사용)
import java.math.BigInteger;
class Solution {
public int solution(int balls, int share) {
int sub = balls - share;
BigInteger answer = Factorial(balls).divide((Factorial(sub).multiply(Factorial(share))));
return answer.intValue();
};
public static BigInteger Factorial(int n) {
BigInteger fac = BigInteger.ONE;
for(int i=n; i>0; i--) {
fac = fac.multiply(BigInteger.valueOf(i));
}
return fac;
}
}
코드에 대해 알아보자.
먼저 주어진 공식을 보면 코드가 한층 더 이해하기 쉽다.
변수 sub을 만들어 n-m 값을 저장한다.
그리고 재귀함수 Factorial을 만들어 팩토리얼 계산을 진행한다.
Factorial 메서드는 BigInteger 변수 ONE을 이용해 1로 지정했다.
그리고 n부터 1까지 차례대로 곱셈을 한다.
그리고 결과값을 반환한다.
BigInteger는 문자열 형태이기 때문에 특정 메서드를 사용해야 한다.
따라서, divide와 multiply라는 메서드를 사용해 나눗셈과 곱셈을 계산했다.
그리고 return 할 때, intValue()를 사용해 정수값으로 반환했다.
BigInteger에 대해 더 알고 싶다면 아래 포스팅을 읽어보는 것을 추천한다.
https://record-study-steadily.tistory.com/72
참고 자료
https://docs.oracle.com/javase/6/docs/api/java/math/BigInteger.html
'Language > Java' 카테고리의 다른 글
[Java] BigInteger를 알아보자 ! (0) | 2023.07.20 |
---|---|
[Programmers] 120908 문자열 안에 문자열 (contains 함수) (0) | 2023.07.16 |
[Java] 문자열에 문자 추가하기 (StringBuilder / +연산자) (0) | 2023.07.12 |