찰떡개발자 코딩

1). 문제 : https://www.acmicpc.net/problem/15649

2). 풀이 : 

왜 풀어도 풀어도 빠르게 안나오는지 ㅠ 휴

사전식으로 정렬된 순서가 있는 조합 즉 순열을 구하는문제이다.

기본적으로 필요한것

1. 숫자가 담겨있는 배열 = arr[]

2. 수열이 만들어질때 담아놓을 빈 배열 = output[]

3. 숫자를 사용했는지 체크여부를 위한 배열 = visited[]

이 세가지를 가지고 지지고 볶으면 된다!.

푸는 방법

1). 먼저 생각해야 될것이 1을 처음에 사용했을때 나머지 2,3 ,3,2 등을 구하는 방법을 생각해야한다.

-> for문으로 시작점(1인지, 2인지....등등)을 돌린다. 

2). 첫번째 index의 숫자를 구하면 해당 depth( 첫번째 index)에 내가 뽑은 숫자를 담아준다.

3). depth를 늘려 2번째 index의 숫자를 결정할껀데, 이때 재귀를 사용하여 나머지 숫자들까지 구하면된다.

4). 각 index별로 순열을 만들었을때 print해주고,

5). 사용했던 숫자도 다음 순열을 만들때 다시 사용해야 되므로 visited[i] = false로 방문여부를 바꿔준다.

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		int[] arr = new int[N];
		int[] output = 	new int[N];
		boolean[] visited = new boolean[N];

		for (int i = 0; i < N; i++) {
			arr[i] = i+1;
		}
		permute(arr,visited,output,0,arr.length,M);
	}

	static void permute(int[] arr, boolean[] visited,int[] output,int depth, int length,int cnt) {
		//종료조건
		if(depth ==cnt) {
			print(output, cnt);
			return;
		}

		//방문한지 안한지 체크 해서 재귀를 돌릴까?
		for (int i = 0; i < length; i++) {
			if(!visited[i] ) {
				visited[i]= true;
				output[depth] = arr[i];
				permute(arr,visited,output,depth+1,length,cnt);
				visited[i]= false;
			}
		}
	}

	static void print(int[] arr , int cnt) {
		for (int i = 0; i < cnt; i++) {
				System.out.print(arr[i]+" ");
		}
		System.out.println();
	}