[백준, BOJ 6443] 애너그램 (java)

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

메모리: 34,256 KB , 시간: 496 ms

사용 알고리즘: 백트래킹, 문자열

728x90

---

입력받은 문자열에서 사용한 문자의 개수를 담는 visited 배열을 만들어,

인덱스에 해당하는 문자가 몇 개 사용됐는지 체크해준다.

 

combi 메소드에서 백트래킹을 통해 현재 사용할 수 있는 문자 중 사전 순으로 빠른 문자부터 스택에 담아주고,

사용할 수 있는 문자 개수를 줄여주며 애너그램 조합을 구해주는 방식을 사용했다.

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

public class Main {

    static char[] string;
    static int[] visited;
    static Stack<Character> stack;
    static StringBuilder result;

    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        result = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

        for (int tc = 0; tc < N; tc++) {
            string = br.readLine().toCharArray();

            // 문자열에 사용된 알파벳 개수
            visited = new int[26];
            for (int i = 0; i < string.length; i++) {
                visited[string[i] - 'a']++;
            }

            stack = new Stack<>();
            combi(0);
        }

        System.out.println(result);
    }

    private static void combi(int n) {

        if(n == string.length) {
            for (char c : stack) {
                result.append(c);
            }
            result.append("\n");
            return;
        }

        for (int i = 0; i < 26; i++) {
            if(visited[i] > 0) {
                visited[i]--;
                stack.push((char)(i + 'a'));
                combi(n + 1);
                visited[i]++;
                stack.pop();
            }
        }
    }
}