[백준] 9742 순열 [자바]

 

---

https://js1jj2sk3.tistory.com/39

백준) 9742 순열

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;


public class Main {
	static char[] s;
	static int[] fac;
	static String result = "";
 	public static void main(String arg[]) throws Exception {
 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 		StringBuilder sb = new StringBuilder();
 		fac = new int[11];
 		fac[0] = 1;
 		for(int i = 1; i <= 10; i++) {
 			fac[i] = fac[i-1] * i;
 		}
 		String input = "";
 		while((input = br.readLine()) != null) {
	 		String temp[] = input.split(" ");
	 		String str = temp[0];
	 		int N = Integer.parseInt(temp[1]);
	 		s = new char[str.length()];
	 		
	 		for(int i = 0; i < str.length(); i++) {
	 			s[i] = str.charAt(i);
	 		}
	 		if(fac[str.length()] < N) {
	 			sb.append(str+" "+N+" = No permutation").append('\n');
	 		}
	 		else {
		 		result = "";
		 		permutation(N-1, str.length());
		 		sb.append(str+" "+N+" = "+result).append('\n');
	 		}
 		}
 		System.out.println(sb);
 	}
 	static void permutation(int n, int len) {
 		int x = n / fac[len-1]; 
 		result += s[x];
 		int cnt = 0;
 		for(int i = 0; i < len; i++) {
 			if(i == x) {
 				continue;
 			}
 			s[cnt++] = s[i];
 		}
 		if(cnt == 1) { //한 개 남았을때
 			result += s[0];
 			return;
 		}
 		permutation(n % fac[len-1], len-1);
 	}
}