Java 백준 1342 행운의 문자열

백준 링크

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

1342번: 행운의 문자열

---

문제

입력

출력

입출력 예시

 

---

제출한 코드

import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static char[] charData;
	static int[] answer;
	static int[] alpha = new int[26];
	static int cnt = 0;
	
	public static void main(String[] args) throws IOException {
		charData = br.readLine().toCharArray();
		for (int i = 0; i < charData.length; i++) {
			alpha[charData[i] - 'a'] += 1;
		}

		answer = new int[charData.length];

		dfs(answer, 0);
		System.out.println(cnt);
	}

	static void dfs(int[] answer, int depth) {
		// 종료 조건
		// 길이가 전체 데이터 길이랑 동일한 경우 종료
		if (depth == charData.length) {
			cnt +=1;
			return;
		}

		// 수행 로직
		for (int i = 0; i < alpha.length; i++) {
			if (alpha[i] != 0 && (depth == 0 || answer[depth - 1] != i)) {
				answer[depth] = i;
				alpha[i] -= 1;
				dfs(answer, depth + 1);
				alpha[i] += 1;
			}
		}
	}

}

 

1. 입력받은 데이터를 char 배열에 저장한다.

2. 입력받은 알파벳의 개수를 세기 위해서 char 배열에 저장된 값을 순회하면서 'a'를 뺀 값을 인덱스로 사용해 값을 1씩 늘려준다.

3. 가능한 경우의 수를 확인하기 위해서 재귀함수를 사용했다.

4. 정답으로 올 수 있는 길이만큼 새로운 조합이 만들어지면 return

5. 알파벳 배열의 길이만큼 순회하면서 새롭게 조합을 만들어 준다.

6. 조건으로는 알파벳이 사용될 수 있는 횟수가 남아있어야 하고 첫 번째 오는 경우이거나 현재 만들어진 answer의 마지막 값과 다른 경우에만 사용될 수 있다.

7. 조건이 만족하면 현재 데이터를 추가해주고 1번 사용이 되었으니 alpha의 값을 1 감소시킨다.

8. 이후 다시 같은 조건으로 재귀함수를 호출해준다.

9. return이 발생하면 사용된 데이터의 횟수를 다시 복구시킨다.