백준 1342_행운의 문자열(JAVA)

 

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

1342번: 행운의 문자열

[문제 풀이]

DFS를 이용하여 문제를 풀었습니다.

 

이 문제는 문자열이 주어졌을 때 두 가지 비교를 통해 행운의 문자열을 찾아내는 것입니다. 

1. 사용할 알파벳이 있느냐

2. 이전 알파벳이 현재 알파벳과 같느냐

 

이 두 가지를 비교해서 만든 문자열이 주어진 문자열의 크기와 같을 경우 결과값을 올려주는 방식으로 문제를 해결했습니다.

 

문제를 푸는 순서는 다음과 같습니다.

• 문자열을 입력 받으면 알파벳의 갯수를 기록한다.
• 알파벳을 하나씩 추가하며, 마지막에 있는 문자와 다른 문자만을 추가한다.
• 주어진 문자열의 크기와 같아지면 결과값을 1 올려준다.

[코드]

package coding;

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

public class Back1342 {

	static char[] alphabet = new char[27];
	static boolean[] visited;
	static int result = 0;
	
	public static void DFS(int idx, String temp, int len) {
		
		if(idx == len) {
			result++;
			return;
		}
		
		for(int i = 0; i < 26; i++) {
			if(alphabet[i] == 0)
				continue;
			if(temp != "" && temp.charAt(temp.length() - 1) == (char)('a' + i))
				continue;
			alphabet[i]--;
			DFS(idx + 1, temp + (char)('a' + i), len);
			alphabet[i]++;
		}
	}
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		
		
		for(int  i = 0; i < str.length(); i++)
			alphabet[str.charAt(i) - 'a']++;

		DFS(0, "", str.length());
		
		System.out.println(result);
		
	}
	
}