[백준][JAVA] 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"을 출력한다.

예제 입력 1 

235 4
bein 20
123456 700
mnpqr 130
tuvwxyz 4000

예제 출력 1 

235 4 = 352
bein 20 = nbie
123456 700 = 651342
mnpqr 130 = No permutation
tuvwxyz 4000 = ywuxvzt

 

코드

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

public class Main {
	private static boolean[] visited;
	private static int n,ans,flag;
	private static char[] word;
	private static char[] arr;

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = "";
		while((input=br.readLine())!=null ) {
			StringTokenizer st = new StringTokenizer(input);
			if(!st.hasMoreTokens()) break;
			word = st.nextToken().toCharArray();
			n = Integer.parseInt(st.nextToken());
			visited = new boolean[word.length];
			ans = 0;
			flag = 0;
			arr = new char[word.length];
			permutation(0);
			if(flag == 0) {
				System.out.print(word);
				System.out.print(" "+ n+" = ");
				System.out.println("No permutation");
			}
		}	
	}
	
	static void permutation(int cnt) {
		if(cnt == word.length) {
			ans++;
			if(ans == n) {
				flag = 1;
				System.out.print(word);
				System.out.print(" "+ n+" = ");
				System.out.println(arr);
                return;
			}
		}
		for (int i = 0; i < word.length; i++) {
			if(!visited[i]) {
				visited[i] = true;
				arr[cnt] = word[i];
				permutation(cnt+1);
				visited[i] = false;
			}
		}
	}
}

 

풀이

재귀를 이용하여 arr의 길이가 주어진 문자열의 길이가 될 때까지 아직 방문하지 않은 문자를 arr에 더해준다.

arr의 길이가 문자열의 길이와 같아지면 count를 증가시키고 이 값이 n과 같으면 이때의 arr를 출력해주고 flag값을 1로 바꾼 뒤 return을 해준다.

모든 경우의 수를 확인한 후에도 count 값이 n과 같아지지 않았다면 flag 값이 0으로 남아있을 것이다. 이 경우 No permutation을 출력한다.