[Baekjoon] 15652번 N과 M(4) (Java)

처음에는  15650 N과 M(2) (Java)에서 난수 뽑기에 중복을 허용하고 경우의 수를 int에서 BigInteger 타입으로 변경하여 

다음과 같이 구현했었다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Random;
import java.math.BigInteger;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int x = scan.nextInt();
		int y = scan.nextInt();

		// 조합 이용
		Random rand = new Random();
		HashSet<String> set = pick(rand, x, y);
		ArrayList<String> al = new ArrayList<>(set);
		Collections.sort(al);							// HashSet을 ArrayList로 변환해서 정렬
		for(int i = 0; i < al.size(); i++) {
			System.out.println(al.get(i));
		}
	}
	
	public static HashSet<String> pick(Random rand, int a, int b) {
		// 뽑을 수 중복조합 경우의 수 -> x+y-1Cy
		BigInteger x = new BigInteger(Integer.toString(a+b-1));
		BigInteger y = new BigInteger(Integer.toString(a-1));
		BigInteger c = new BigInteger(Integer.toString(b));
		BigInteger fac = fac(x).divide(fac(y).multiply(fac(c)));
		
		HashSet<String> set = new HashSet<String>();	
		BigInteger size = new BigInteger(Integer.toString(set.size()));
		while(size.compareTo(fac) == -1) {							// set을 이용하여 숫자 조합 중복 방지
			int[] intArr = new int[b];
			for(int i = 0; i < b; i++) {
				int rnd = rand.nextInt(a) + 1;				// 1 ~ x까지 난수
				intArr[i] = rnd;
			}
			Arrays.sort(intArr);							// 오름차순 정렬
			String str = "";
			for(int i = 0; i < b; i++) {
				str += intArr[i] + " ";
			}
			set.add(str.substring(0, str.length()-1));		// 마지막 공백 제거해서 add
			size = new BigInteger(Integer.toString(set.size()));
		}
		return set;
	}
	
	public static BigInteger fac(BigInteger n) {
		if(n.compareTo(new BigInteger("0")) == 1) {	// a.compareTo(b) -> a=b : 0, a>b : 1, a<b : -1
			return n.multiply(fac(n.subtract(new BigInteger("1"))));
		}else {
			return new BigInteger("1");
		}
	}
}

당연히 testcase와 8 6 등 큰 수를 입력해도 결과는 잘 나왔지만 당황스럽게도 시간 초과에 걸렸다.

연산이 너무 많다보니 어쩌면 당연한 결과였다.....

 

 

그래서 다음과 같은 방법으로 시도하였더니 시간도 맞고 코드도 엄청나게 간결해졌다.

package Q15652;

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	public static int x;
	public static int y;
	public static int[] intArr;
	public static ArrayList<String> arr;
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		x = scan.nextInt();
		y = scan.nextInt();
		
		intArr = new int[y];
		arr = new ArrayList<String>();
		dfs(1, 0);		// 1, 1 / 1, 2 등과 같이 숫자 1부터 시작
		for(int i = 0; i < arr.size(); i++) {
			System.out.println(arr.get(i));
		}
	}
	
	public static void dfs(int k, int depth) {
		if(depth == y) {
			String str = "";
			for(int i = 0; i < intArr.length; i++) {
				str += intArr[i] + " ";
			}
			arr.add(str.substring(0, str.length()-1));	// 마지막 공백 제거
			return;					// 호출한 곳으로 되돌아감(for문)
		}
		for(int i = k; i <= x; i++) {// x만큼 실행
			intArr[depth] = i;
			dfs(i, depth + 1);			// 재귀호출
		}
    }
}