자바 순열 조합 암기하면 좋은 메소드

자바는 내장함수로 순열, 조합이 없기 때문에 필요시 구현할 줄 알아야 한다.

방문탐색을 통해 구현하는 순열, 조합 코드

import java.util.Arrays;

public class Perm_Combi {

	static int N;
	static int R;
	static int[] input; //길이 N 뽑을 대상
	static int[] numbers;//길이 R 뽑힌 것
	static boolean[] isSelect; //선택된거 기억

	public static void main(String[] args) {
		N = 4;
		R = 3;

		input = new int[N];
		isSelect = new boolean[N];
		numbers = new int[R];

		for (int i = 0; i < N; i++) {
			input[i] = i;
		}
		
		perm(0);
		System.out.println();
		combi(0, 0);
		System.out.println();
		subset(0);
	}

	public static void combi(int cnt, int start) {
		if (cnt == R) {
			System.out.println(Arrays.toString(numbers));
			return;
		}
		for (int i = start; i < N; i++) {
			numbers[cnt] = input[i];
			combi(cnt + 1, i + 1);
		}
	}

	public static void perm(int cnt) {
		if (cnt == R) {
			System.out.println(Arrays.toString(numbers));
			return;
		}

		for (int i = 0; i < N; i++) {
			if (isSelect[i])
				continue;
			numbers[cnt] = input[i];
			isSelect[i] = true;
			perm(cnt + 1);
			isSelect[i] = false;

		}

	}
	
	public static void subset(int idx) {
		if(idx==N) {
			for(int i = 0 ; i < N ; i++) {
				System.out.print(isSelect[i]?input[i]+", ":"");
			}
			System.out.println();
			return;
		}
		isSelect[idx] = true;
		subset(idx+1);
		isSelect[idx] = false;
		subset(idx+1);
	}
}

방문탐색을 사용하면 사이에 가지치기나 특별한 조건을 넣기 더 편하기 때문에 코딩테스트에 사용하기 편하다.

순열의 특징

static int[][] table = new int[30][30];

......

for(int i = 0; i < table.length;i++) {
			table[i][0]=1;
			table[i][i]=1;
		}
for(int i = 2; i < 30 ; i++) {
			for(int j = 1; j < 30; j++) {
				table[i][j] = table[i-1][j]+table[i-1][j-1];
			}
		}
        
table[N][R] -> nCr

간단히 경우의 수를 구하고자 할 경우 순열의 특징을 이용하면 문제를 풀 수 있다.