Troubleshooting
class Solution {
public int solution(int balls, int share) {
return factorial(balls) / (factorial(balls - share) * factorial(share));
}
public int factorial(int n) {
if(n == 1) return 1;
return n*factorial(n-1);
}
}여러 테스트케이스에서 틀렸는데, 모르겠어서 질문게시판을 조금 찾아봤다.
이런 힌트를 얻을 수 있었다. (감사합니다!)
n개의 연속된 정수에는 항상 n의 배수가 포함되기 때문에 항상 정수 값이 나와서 부동소수점 문제를 피할 수 있습니다.
-> 이 문장이 핵심 포인트이다!
Troubleshooting 2
class Solution {
public int solution(int balls, int share) {
int answer = 1;
for(int i=1; i<= share; i++) {
answer *= balls;
answer /= i;
balls--;
}
return answer;
}
}몇개의 테스트케이스에서 틀렸다.
하나 놓친게있다. 계산 과정에서 int를 넘을 수 있다.
answer, solution의 반환값을 모두 int에서 long으로 수정했다.
(이건 원래 틀로 주어졌던 부분인데 마음대로 이렇게 수정해도되나..?)
-> 해결!
아래 코드는 기존 주어진 틀을 조금 수정하는게 찝찝해서 수정한 코드다.
중간 다리 역할하는 long 타입의 result 변수를 추가했다.
class Solution {
public int solution(int balls, int share) {
int answer = 1;
long result = 1L;
for(int i=1; i<= share; i++) {
result *= balls;
result /= i;
balls--;
}
answer = (int)result;
return answer;
}
}다른 풀이를 구경하다가 조금 추가하면 좋을것같아서 가져왔다.
for문에서 반복횟수를 조금이라도 줄이려면, balls-share, share중에 더 작은것을 골라 그 횟수만큼 반복해도된다.
즉, 조합이므로 분모에 (balls-share)!, share!가 들어가는데, 이 둘중 하나는 미리 나누고 시작하기때문에, 더 큰수로 먼저 나눴다고 생각하고 둘 중 작은것을 골라 그 수만큼 반복하자.
share = Math.min(balls - share, share);이 코드 하나만 추가하면된다.
class Solution {
public int solution(int balls, int share) {
int answer = 1;
share = Math.min(balls - share, share);
long result = 1L;
for(int i=1; i<= share; i++) {
result *= balls;
result /= i;
balls--;
}
answer = (int)result;
return answer;
}
}