[BAEKJOON 백준] 9742 순열

www.acmicpc.net/problem/9742

9742번: 순열

 

 

문제

집합의 순열이란 집합의 서로 다른 원소를 모두 사용해 만들 수 있는 순서이다. 예를 들어, {2,3,5}의 순열은 다음과 같다.

1. 2 3 5
2. 2 5 3
3. 3 2 5
4. 3 5 2
5. 5 2 3
6. 5 3 2

각각의 순열은 숫자로 나타낼 수 있다. 위의 순열은 사전순으로 쓰여져 있으며, 등장하는 순서를 이용해 나타낸다. 즉, 3 5 2는 위치 4에 있고, 5 3 2는 마지막 위치인 6에 있다.

{b,e,i,n}으로 만들 수 있는 순열은 다음과 같다.

1. b e i n
2. b e n i
3. b i e n
4. b i n e
5. b n e i
6. b n i e
7. e b i n
8. e b n i
9. e i b n
10. e i n b
11. e n b i 
12. e n i b
13. i b e n
14. i b n e
15. i e b n
16. i e n b
17. i n b e
18. i n e b
19. n b e i
20. n b i e
21. n e b i
22. n e i b
23. n i b e
24. n i e b

서로 다른 숫자와 문자로 이루어진 집합과 위치가 주어졌을 때, 그 집합의 순열 중 주어진 위치의 순열을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 문자열은 서로 다른 숫자와 알파벳으로 이루어져 있으며, 길이는 최대 10이다. 또한, 사전순 순서대로 주어진다. 문자열 다음에는 찾아야 하는 위치가 주어지며, 이 값은 3,628,800보다 작거나 같은 자연수이다.

출력

각각의 테스트 케이스마다, 입력으로 주어진 위치에 해당하는 순열을 공백없이 출력한다. 만약, 해당하는 순열이 없는 경우에는 "No permutation"을 출력한다.

 

 

순열을 구하는 문제이다.

순열을 구하기 위해서는 DFS 방식으로 문제를 풀어야 한다.

 

순열의 경우 중복이 있으면 안되기 때문에 visit배열을 이용을 해서 순열을 만들때 중복이 생기지 않도록 주의해야 한다.

 

그리고 순열이 없는 경우에는 No permutation을 출력하도록 했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	private static int N;
	private static String arr[];
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String line=null;
		while((line=br.readLine())!=null) {
			StringTokenizer st=new StringTokenizer(line," ");
			String temp=st.nextToken();
			arr=temp.split("");
			time=0;
			temparr=new String[arr.length];
			visit=new boolean[arr.length];
			N=Integer.parseInt(st.nextToken());
			find(0);
			
			System.out.print(temp+" "+N+" = ");
			if(time<N) {	//순열이 없을 경우
				System.out.println("No permutation");
			}else {	//순열이 있을 경우
				
				for (int j = 0; j < arr.length; j++) {
					System.out.print(arr[j]);
				}
				System.out.println();
			}
			
		}
	}
	private static String temparr[];
	private static boolean visit[];
	private static int time;
	private static void find(int cnt) {
		// TODO Auto-generated method stub
		if(cnt==arr.length) { //순열이 만들어 졌을 경우
			time++;	//순열의 수를 세어준다.
			if(time==N) {	//해당 위치랑 같다면 결과 배열에 저장을 해준다.
				for (int i = 0; i < arr.length; i++) {
					arr[i]=temparr[i];
				}
				
			}
			return;
		}
		for (int i = 0; i < arr.length; i++) {	// 순열을 만들어 주는 작업이다.
			if(visit[i])continue;	//visit 배열이 true면 무시한다.
			temparr[cnt]=arr[i];	//임시배열에 순열을 저장해 준다.
			visit[i]=true;
			find(cnt+1);
			visit[i]=false;
		}
	}
}