[백준]#1342 행운의 문자열

문제

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

입력

첫째 줄에 문자열 S가 주어진다. 길이는 최대 10이다.

출력

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

예제 입력 1

aabbbaa

예제 출력 1

1

풀이

이 문제는 next_permutation 알고리즘을 이용해서 풀 수 있었다. next_permutation 알고리즘이 익숙치 않아서 어려웠고 C++에는 라이브러리가 있지만 Java는 직접 구현해야한다.

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

public class Main {
    static char[] arr;
    static int ans = 0;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        arr = new char[input.length()];
        for(int i=0; i<input.length(); i++)
            arr[i] = input.charAt(i);

        Arrays.sort(arr);

        if(check(arr)) ans++;

        while(nextPermutation()) {}

        System.out.println(ans);
    }

    public static boolean check(char[] target) {
        for (int i=0; i<target.length-1; i++) {
            if (target[i]==target[i+1]) return false;
        }

        return true;
    }

    public static boolean nextPermutation() {
        int i = arr.length - 1;
        while (i > 0 && arr[i-1] >= arr[i]) {
            i--;
        }

        if (i <= 0)
            return false;

        int j = arr.length - 1;
        while (arr[j] <= arr[i-1]) {
            j--;
        }

        char temp = arr[i-1];
        arr[i-1] = arr[j];
        arr[j] = temp;

        j = arr.length - 1;
        while (i < j) {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }

        if(check(arr))
            ans++;

        return true;
    }
}