자바에서 순열과 조합

요즘은 자바로 코테를 준비하고 있는데 매 순간이 경악의 연속이다. 자바는 놀랍게도 순열, 조합 라이브러리가 없어서 파이썬이면 1줄만에 끝나는 뽑기를 직접 한땀한땀 구현해야 한다.

아무튼 몇 번 자바로 이런 문제를 풀다보니 손에 익은 풀이가 생겨서 정리하려고 한다. 인터넷 허용 안되는 시험이라면 그때그때 상황에 맞게 효율적으로 짜겠지만...인터넷 허용이라면 이 포스팅의 순열,조합 함수를 긁어 쓸 생각이다.^_^

뭘 뽑을지는 문제마다 다르므로 차라리 사용할 인덱스만 뽑아서 output 배열에 넣는게 다양한 문제에 적용하기 좋을 것 같다.(0,1,2...~n중 r개를 뽑기)

순열

 
import java.util.*;
import java.io.*;

public class Main {
	public static int [] index;
	public static int [] output;
	public static int n,r;
	public static boolean [] visited;
	public static void main(String[] args) throws Exception {
		//n개 중 r개를 뽑는다. 문제에 따라 바꿔 주기.
		 n=3;
		 r=2;
		 output=new int[r];
		 visited=new boolean[n];
		 
		 perm(0);
	}
	//순열
	public static void perm(int cnt) {
		if(cnt==r) {
			//뽑힌 인덱스의 목록
			System.out.println(Arrays.toString(output));
			return;
		}
		for(int i=0;i<n;i++) {
			if(visited[i]) continue; 
			output[cnt]=i;
			visited[i]=true;
			perm(cnt+1);
			visited[i]=false;
		}
	}
 
}

조합

import java.util.*;
import java.io.*;

public class Main {
	public static int [] index;
	public static int [] output;
	public static int n,r;
	public static void main(String[] args) throws Exception {
		//n개 중 r개를 뽑는다. 문제에 따라 바꿔 주기.
		 n=3;
		 r=2;
		 output=new int[r];
		 combi(0,0);
	}
	//조합
	public static void combi(int cnt,int start) {
		if(cnt==r) {
			//뽑힌 인덱스의 목록
			System.out.println(Arrays.toString(output));
			return;
		}
		for(int i=start;i<n;i++) {		 
			output[cnt]=i;
			combi(cnt+1,i+1);
			 
		}
	}
 
}

조합은 start 인덱스를 두고 거기서부터 탐색하므로 방문체크가 필요 없다.

순열과 조합의 시간복잡도

순열의 시간복잡도는 O(n!) 이고 조합의 시간복잡도는 O(2^n) 이다.

그리고 얘네들은 흔히 볼 수 있는 시간복잡도 그래프에서 거의 직선을 그리고 있다. 둘 다 O(n^2)보다 비효율적이다.

예를 들어 순열의 경우...12!정도만 되어도 5억이다. n이 10이 넘어간다면 순열, 조합 문제가 맞는지 다시 한 번 생각해봐야 한다. 조합은 순열보단 상황이 낫지만 30/15 정도만 되어도 터진다고 보는게 맞다.

단 r이 단 2개..이런식으로 정해져있는 경우에는 n이 10을 넘어도 순열, 조합 문제가 맞을 수도 있다. 마지노선을 1억정도로 잡고 상황에 따라 시간복잡도를 생각해 보는게 바람직할 것 같다.