[ BOJ ][JAVA][6443] 애너그램

www.acmicpc.net/problem/6443

6443번: 애너그램

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	1096	390	296	41.926%

문제

씬디는 애너그램(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

코드

import java.io.*;
import java.util.*;

public class p6443 {
    static int n;
    static char[] cArr, result, mx;
    static boolean[] visit;
    static BufferedWriter bw;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        while (n-- > 0) {
            cArr = br.readLine().toCharArray();
            int len = cArr.length;
            result = new char[len];
            mx = new char[len];
            visit = new boolean[len];

            Arrays.sort(cArr);

            dfs(len, 0);
        }
        bw.flush();
        bw.close();
        br.close();
    }
    static void dfs(int len, int depth) throws IOException {
        if (depth == len) {
            bw.write(result);
            bw.write("\n");
            return;
        }

        mx[depth] = 0;
        for (int i = 0; i < len; i++) {
            if (visit[i]) continue;
            if (mx[depth] >= cArr[i]) continue; // mx 함수로 중복 순열을 제거

            mx[depth] = cArr[i];

            visit[i] = true;
            result[depth] = cArr[i];
            dfs(len, depth + 1);
            visit[i] = false;
        }
    }
}

우선순위 큐 풀이

import java.io.*;
import java.util.*;
public class Main {
    static int n,t;
    static String s;    
    static boolean[] v;
    static int[] alpa;
    static StringBuilder sb=new StringBuilder();
    static void dfs(int idx,String str){
        if(idx==n){
            sb.append(str+"\n");
            return;
        }
        for(int i=0;i<26;i++){
            if(alpa[i]>0){
                alpa[i]--;
                dfs(idx+1,str+((char)('a'+i)+""));
                alpa[i]++;
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(bf.readLine());       
        t=Integer.parseInt(st.nextToken());
        for(int tt=0;tt<t;tt++){
            st=new StringTokenizer(bf.readLine());       
            s=st.nextToken();            
            n=s.length();
            v=new boolean[n]; 
            alpa=new int[26];           
            PriorityQueue<Character>pq=new PriorityQueue<>();
            for(int i=0;i<n;i++)alpa[s.charAt(i)-'a']++;            
            dfs(0,"");
        }
        System.out.println(sb);
    }    
}

순열 풀이

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;
    }
}