[백준]1010번 다리놓기 풀이 코드/입출력 방식에 따른 성능 개선

https://www.acmicpc.net/problem/1010

 

순서에 상관 없이 m개 중 n개를 고르는 조합 수를 묻는 문제다. 아래 공식을 사용한다. 

 

재귀함수를 이용해 팩토리얼을 구하는 메소드를 따로 만들어서 풀었다.  

import java.math.BigInteger;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int a = scanner.nextInt();
        
        for(int i=0; i < a; i++) {
            int n = scanner.nextInt();
            int m = scanner.nextInt();
            System.out.println(fact(m).divide(fact(m-n).multiply(fact(n))));
        }
 
        
        scanner.close();
    }
    
    public static BigInteger fact(int n) {
        if(n<=1) {
            return BigInteger.valueOf(1);
        } else {
            return fact(n-1).multiply(BigInteger.valueOf(n));
        }
    }
}

처음에 모든 타입을 int로 뒀는데 오류가 나서 출력을 해봤더니 팩토리얼 값이 음수로 나왔다. 

int 범위를 초과해서 그런 것이다. long을 사용해도 마찬가지여서 BigInteger를 사용했다. 

백준 몇 문제 안풀어봤는데 범위때문에 BigInteger 쓸 일이 꽤 있는 것 같다. 

 

---

다음은 입력을 Scanner 대신 BufferedReader로 받은 결과이다. 

그 아래는 출력을 StringBuilder로 한번에 한 결과이다. 

입출력이 빈번한 경우

같은 알고리즘에 입출력방식만 적절히 바꿔도 성능이 개선됨을 알 수 있었다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        // Scanner scanner = new Scanner(System.in);
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        
        while(T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            //System.out.println(fact(m).divide(fact(m-n).multiply(fact(n))));
            sb.append(fact(m).divide(fact(m-n).multiply(fact(n)))).append('\n');
        }
        System.out.println(sb);
    }
    
    public static BigInteger fact(int n) {
        if(n<=1) {
            return BigInteger.valueOf(1);
        } else {
            return fact(n-1).multiply(BigInteger.valueOf(n));
        }
    }
}