9742번: 순열

https://www.acmicpc.net/problem/9742

9742번: 순열

• 풀이

주어진 문자열에 대한 모든 순열을 찾는 재귀함수를 작성한다.

찾은 문자열의 개수를 받는 변수 num을 만들어준 뒤, num이 N번째일 때 해당 순열을 출력하고 재귀를 멈춘다.

만약 모든 순열을 찾았는데도 N번째가 되지 못한 경우 No permutation을 출력한다.

 

+ 입력값의 개수가 정해져있기 않기 때문에 EOF 처리가 필요하다.

EOF 처리

• 코드

1. Scanner 사용

import java.io.IOException;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
	static int N; // 찾아야 하는 위치
	static String str; // 주어진 문자열
	static char[] charArr; // 주어진 문자열을 배열로 변환
	static char[] resultArr; // 출력될 순열 배열
	static boolean [] isSelected; // 해당 알파벳이 선택되었는 지 체크
	static boolean isChecked; // N에 해당하는 순열을 찾았는 지 체크
	static int num; // 순열 등장 순서
	
	static void permutation(int r) {
		if (r==charArr.length) { // 재귀 종료 조건
			num++;
			if (num==N) { // N 번째 순열인 경우 출력 후 return;
				System.out.print(str + " " + N + " = ");
				for(int i=0; i<charArr.length;i++) System.out.print(resultArr[i]);
				System.out.println();
				isChecked = true;
				return;
			}
			return;
		}
		
		for (int i = 0; i<charArr.length; i++) {
			if (isSelected[i]) continue; // 이미 선택된 문자라면 break
			resultArr[r] = charArr[i]; // 결과 배열에 해당 문자 넣기
			isSelected[i] = true; // 선택
			permutation(r+1); // 재귀
			isSelected[i] = false; // 선택 해제
		}
	}

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);

		while (sc.hasNextLine()) { // EOF 처리
			StringTokenizer st = new StringTokenizer(sc.nextLine());
			str = st.nextToken();

			// 변수 초기화
			N = Integer.parseInt(st.nextToken());
			charArr = new char[str.length()];
			charArr = str.toCharArray();
			resultArr = new char[str.length()];
			isSelected = new boolean[str.length()];
			num = 0;
			isChecked = false;
				
			// 순열
			permutation(0);
			
			// 찾아야되는 순열을 찾지 못한 경우
			if (!isChecked) {
				System.out.print(str + " " + N + " = No permutation");
				System.out.println();
			}
		}
	}
}

2. BufferedReader 사용

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

public class Main {
	static int N; // 찾아야 하는 위치
	static String str; // 주어진 문자열
	static char[] charArr; // 주어진 문자열을 배열로 변환
	static char[] resultArr; // 출력될 순열 배열
	static boolean [] isSelected; // 해당 알파벳이 선택되었는 지 체크
	static boolean isChecked; // N에 해당하는 순열을 찾았는 지 체크
	static int num; // 순열 등장 순서
	
	static void permutation(int r) {
		if (r==charArr.length) { // 재귀 종료 조건
			num++;
			if (num==N) { // N 번째 순열인 경우 출력 후 return;
				System.out.print(str + " " + N + " = ");
				for(int i=0; i<charArr.length;i++) System.out.print(resultArr[i]);
				System.out.println();
				isChecked = true;
				return;
			}
			return;
		}
		
		for (int i = 0; i<charArr.length; i++) {
			if (isSelected[i]) continue; // 이미 선택된 문자라면 break
			resultArr[r] = charArr[i]; // 결과 배열에 해당 문자 넣기
			isSelected[i] = true; // 선택
			permutation(r+1); // 재귀
			isSelected[i] = false; // 선택 해제
		}
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
		String input = "";
			
		while ((input = bf.readLine())!= null && input.length() != 0) {
			st = new StringTokenizer(input);
			str = st.nextToken();

			// 변수 초기화
			N = Integer.parseInt(st.nextToken());
			charArr = new char[str.length()];
			charArr = str.toCharArray();
			resultArr = new char[str.length()];
			isSelected = new boolean[str.length()];
			num = 0;
			isChecked = false;
				
			// 순열
			permutation(0);
			
			// 찾아야되는 순열을 찾지 못한 경우
			if (!isChecked) {
				System.out.print(str + " " + N + " = No permutation");
				System.out.println();
			}
		}
	}
}