[BOJ_6443] 애너그램

설명

---

중복 제거를 줄이기 위해 처음에는 그냥 알파벳의 index 위치로 탐색했다가 메모리 초과가 나서 다시 생각해서 풀어보았다. 아래와 같이 알파벳의 갯수에 대해서 카운트 하면 a -> a -> b 와 같은 것이 한 번 더 나올 수가 없다.

 

뒤로 돌아갔을때 만일 index 위치로 탐색하면 처음 나온 a와 뒤에 나온 a 값이 다른 것인데 알파벳의 count 값으로 방문 선정을 해버리면 처음에 나온 a와 뒤에 나온 a는 모두 같은 경우이다. (for문 내부에서 넘어가는 i 값이 달라져 버리니... 다음번에 선택을 할 수 밖에 없다.)

 

 

 

코드

---

package backtracking;

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

public class BOJ_6443 {
    static char[] crr;
    static int[] visited;
    static StringBuilder sb;
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");
        int N = Integer.parseInt(tk.nextToken());
        sb = new StringBuilder();
        for(int i = 0; i < N; i++){
            tk = new StringTokenizer(in.readLine()," ");
            String str = tk.nextToken();
            crr = str.toCharArray();
            visited = new int[26];
            for(char now : crr){
                visited[now - 'a']++;
            }
            go(0,"");
        }
        System.out.println(sb.toString());
    }

    private static void go(int idx,String str) {
        if(idx == crr.length){
            sb.append(str + "\n");
            return;
        }
        for(int i = 0; i < 26; i++){
            if(visited[i] > 0){
                visited[i]--;
                go(idx + 1, str + (char) ('a'+ i));
                visited[i]++;
            }
        }
    }
}