[Baekjoon] 14534_String Permutation

문제(출처: https://www.acmicpc.net/problem/14534)

---

< String Permutation >

 

문제 풀이 

 

문자열의 모든 순열을 구한다.

 

my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;

public class _14534_ { // String Permutation
	static char result[];
	static boolean visited[];
	static ArrayList<String> answer;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int T = Integer.parseInt(bf.readLine());

		for (int i = 0; i < T; i++) {
			bw.write("Case # " + (i + 1) + ":\n");
			String str = bf.readLine();

			char[] arr = str.toCharArray();
			visited = new boolean[arr.length];
			result = new char[arr.length];
			answer = new ArrayList<>();
			permutation(arr, 0);

			for (String x : answer) {
				bw.write(x + "\n");
			}
		}
		bw.flush();
	}

	private static void permutation(char[] arr, int index) {
		if (index == arr.length) {
			answer.add(new String(result));
			return;
		}
		for (int i = 0; i < arr.length; i++) {
			if (!visited[i]) {
				visited[i] = true;
				result[index] = arr[i];
				permutation(arr, index + 1);
				visited[i] = false;
			}
		}
	}
}

 

변수)
T : 테스트 케이스 수
str : 입력 문자열
arr : 문자열 -> char 배열
visited : 방문 여부
result : 순열
answer : 순열을 저장한 ArrayList

 

테스트 케이스 수 T를 입력받아 T 만큼 다음 과정을 반복한다.

 

1) 문자열 입력

2) permutation 함수 호출

3) ArrayList 값 출력

 

permutation(char 배열, index)

index가 배열 길이와 같다면 ArrayList에 char[] result 값을 String으로 변환하여 저장한다.

배열을 전체 탐색하며 아직 방문하지 않은 곳이면 방문 처리 및 result[index]에 arr[i]값을 저장하고 다음 값을 구하기 위해 permutation을 호출한다. 호출 후 visited를 다시 false로 저장한다.

---

---