[오늘의 문제] 행운의 문자열

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

선겸이와 준환이는 자기 방에서 문자열을 공부하고 있다. 선겸이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준환이는 문자열 S를 분석하기 시작했다. 준환이는 문자열 S에 나오는 문자를 재배치하면 서로 다른 행운의 문자열이 몇 개 나오는지 궁금해졌다. 만약 원래 문자열 S도 행운의 문자열이라면 그것도 개수에 포함한다.

입력 형식
첫째 줄에 문자열 S가 주어진다. S의 길이는 최대 10이고, 알파벳 소문자로만 이루어져 있다.

출력 형식
첫째 줄에 위치를 재배치해서 얻은 서로 다른 행운의 문자열의 개수를 출력한다.

예제 입력 1
aabbbaa
예제 출력 1
1
예제 입력 2
ab
예제 출력 2
2
예제 입력 3
aaab
예제 출력 3
0
예제 입력 4
abcdefghij
예제 출력 4
3628800

import java.util.*;

public class Main {

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String input = sc.next();
    int result = countLuckyPermutations(input);
    System.out.println(result);  // 결과 출력
}

public static int countLuckyPermutations(String s) {
    char[] chars = s.toCharArray();
    Arrays.sort(chars);  // 입력 문자열 정렬
    boolean[] used = new boolean[chars.length];
    return generatePermutations(chars, "", used, '\0');
}

public static int generatePermutations(char[] chars, String current, boolean[] used, char lastChar) {
    if (current.length() == chars.length) {
        return 1;
    }

    int count = 0;
    for (int i = 0; i < chars.length; i++) {
        // 인접한 문자열이 다른 행운 문자열을 구성해야 합니다. 이전 문자와 동일하면 비교할 필요가 없습니다.
        if (used[i] || (i > 0 && ____ && !used[i - 1])) {
            continue;
        }
        // 추가될 문자와 생성된 순열의 마지막 글자가 같다면 의미없겠죠?
        if (current.length() > 0 && ____) {
            continue;
        }

        used[i] = true;
        // 현재 문자를 추가하여 다시 순열을 생성
        count += generatePermutations(chars, ____, used, chars[i]);
        used[i] = false;
    }

    return count;
}

}

빈칸1: X
정답: chars[i] == chars[i - 1]
해설: chars[i] == chars[i - 1]는 현재 문자와 이전 문자가 동일한지를 확인합니다. 이 조건은 정렬된 chars 배열에서 중복된 문자를 처리하기 위해 필요합니다. 만약 이전 문자가 사용되지 않았다면(!used[i - 1]), 이전 문자와 동일한지를 확인하고 현재 문자를 건너뛰어 중복된 순열 생성을 방지합니다.
-> 나는 lastChar == chars[i]로 골랐다. lastChar이 이전문자라는 변수로 착각했는데 아녔다. 초기값이 lastChar == null일 가능성이 크다.

빈칸2: O
정답: chars[i] == lastChar
해설: chars[i] == lastChar는 현재 문자가 직전에 추가된 문자와 동일한지를 확인합니다. 이 조건은 "행운의 순열" 조건(인접한 문자가 같으면 안 됨)을 만족시키기 위해 필요합니다.

빈칸3: O
정답: current + chars[i]
해설: current + chars[i]는 현재 생성된 순열에 새로 선택한 문자를 추가하여 다음 재귀 호출로 전달합니다.