백준 1342번: 행운의 문자열

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

 

알파벳 소문자로 이루어진 단어를 인접한 문자가 같지 않게 재배치하는 모든 경우의 수의 갯수를 구하는 문제이다. 문자의 길이가 10 이하이므로 백트래킹을 이용하여 마지막 문자와 비교하여 풀면 된다.

 

단어에 있는 모든 알파벳의 갯수 정보는 int[]에 index는 [알파벳-'a'] 으로 대입하여 저장한다.

String word = br.readLine();
int[] board = new int[26];
for (int i = 0; i < word.length(); i++) {
    board[word.charAt(i) - 'a']++;
}

 

 

백트래킹은 알파벳 갯수, 단어의 길이, 현재 길이, 마지막 문자를 매개변수로 하여 추적하며, 갯수가 1 이상이면서 직전 알파벳과 다른 알파벳을 찾아 백트래킹한다. 단어의 길이와 현재 길이가 같으면 행운의 문자열을 1개 완성한 것이므로 1을 반환한다.

private static int backtracking(int[] board, int length, int current, int last) {
    if (current == length) {
        return 1;
    }
    
    int count = 0;
    for (int i = 0; i < 26; i++) {
        if (board[i] <= 0 || i == last) {
            continue;
        }
        board[i]--;
        count += backtracking(board, length, current + 1, i);
        board[i]++;
    }
    return count;
}

 

 

결과 코드는 다음과 같다.

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

public class 행운의문자열1342 {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String word = br.readLine();
        br.close();
        int[] board = new int[26];
        for (int i = 0; i < word.length(); i++) {
            board[word.charAt(i) - 'a']++;
        }
        System.out.print(backtracking(board, word.length(), 0, -1));
    }
    
    private static int backtracking(int[] board, int length, int current, int last) {
        if (current == length) {
            return 1;
        }
        
        int count = 0;
        for (int i = 0; i < 26; i++) {
            if (board[i] <= 0 || i == last) {
                continue;
            }
            board[i]--;
            count += backtracking(board, length, current + 1, i);
            board[i]++;
        }
        return count;
    }
}