[백준]#6443 애너그램

문제

씬디는 애너그램(anagram) 프로그램을 만들어 줄 수 있는 남자를 좋아한다. 참고로 씬디는 매우 예쁘다.

애너그램 프로그램이란, 입력받은 영단어의 철자들로 만들 수 있는 모든 단어를 출력하는 것이다. 가령 "abc" 를 입력받았다면, "abc", "acb", "bac", "bca", "cab", "cba" 를 출력해야 한다.

입력받은 단어내에 몇몇 철자가 중복될 수 있다. 이 경우 같은 단어가 여러 번 만들어 질 수 있는데, 한 번만 출력해야 한다. 또한 출력할 때에 알파벳 순서로 출력해야 한다.

입력

첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다. 영단어는 소문자로 이루어져 있다.

출력

N개의 영단어에 대한 모든 가능한 애너그램을 출력한다. 각각의 영단어에 대한 애너그램을 출력할 때, 알파벳 순서로 중복되지 않게 출력한다.

예제 입력 1

2
abc
acba

예제 출력 1

abc
acb
bac
bca
cab
cba
aabc
aacb
abac
abca
acab
acba
baac
baca
bcaa
caab
caba
cbaa

풀이

이 문제는 순열을 통해 순서대로 모든 문자 배열을 구하는 문제였다. 그냥 순열보다 더 빠르게 구현하기 위해서 Next-Permutation 알고리즘을 사용해서 풀었다.

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

public class Main {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for(int i=0; i<T; i++) {
            String input = br.readLine();
            StringBuilder sb = new StringBuilder();
            char[] arr = new char[input.length()];
            for(int j=0; j<arr.length; j++)
                arr[j] = input.charAt(j);

            Arrays.sort(arr);

            for(int j=0; j<arr.length; j++)
                sb.append(arr[j]);
            sb.append("\n");

            while(next_permutation(arr)) {
                for(int j=0; j<arr.length; j++)
                    sb.append(arr[j]);
                sb.append("\n");
            }

            System.out.print(sb.toString());
        }
    }

    public static boolean next_permutation(char[] arr) {
        int i = arr.length-1;

        while(i>0 && arr[i]<=arr[i-1])
            i--;                          //앞의 문자보다 뒤에 문자가 사전상 뒤에 오는 경우 탐색

        if(i<=0) return false;

        int j = arr.length-1;

        while(arr[i-1]>=arr[j])
            j--;                          //선택한 문자보다 사전상 뒤에 오는 문자를 배열 끝에서부터 탐색

        char temp = arr[j];
        arr[j] = arr[i-1];
        arr[i-1] = temp;                //두 문자를 서로 교환

        j = arr.length-1;
        while(i<j) {
            temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;              //뒤에 문자들 순서를 뒤집어 줌
            i++;
            j--;
        }

        return true;
    }
}