[JAVA] 6443. 애너그램

처음에는 입력받는 문자열의 문자를 배열에 저장하였고, 중복을 줄이기 위해 set을 이용했으나 메모리 초과가 나왔다.

예상은 했으나 딱히 다른 방법이 생각나지 않았다.

 

검색을 해보니 방식은 26개의 알파벳으로 한정되어있기 때문에 26개의 배열을 마련하고 거기서 해당 문자의 수만큼 배열의 값을 증가시키는 방식을 통해 구현하였고, 그렇게 되면 for문을 돌리면 해당 알파벳의 배열에서 값이 0보다 크면 그 알파벳을 사용하고 아니면 사용하지 못하며, 중복을 방지할 수 있다.

 

즉, 알파벳 하나씩을 배열에 넣으면 arr[0]도 arr[1] 도 a를 가지고 있다면 for문을 통해 중복이 되지만, arr[0]에 2라는 값으로 2번 들어있다는 것을 의미하면 for문은 0일 때만 a를 선택하므로 중복을 없앨 수 있게 되는 것이다.

 

char[] word 배열을 통해 sb.append(word)를 이용해 string을 출력하였다.

반드시 배열 이름 하나만을 append에 넣어야 string으로 출력된다.

 

 

package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class B_6443_애너그램 {
 
    static StringBuilder sb;
 
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        int N = Integer.parseInt(in.readLine());
        for (int i = 0; i < N; i++) {
            String str = in.readLine();
            int[] c = new int[26]; // 알파벳 수만큼
            for (int j = 0; j < str.length(); j++) {
                int num = str.charAt(j) - 'a'; // 숫자로 변경
                c[num]++; // 반복되는 만큼 수를 올림
            }
            char[] word = new char[str.length()]; // 완성해 나아갈 단어
            solve(0, str.length(), word, c);
        }
        System.out.println(sb);
    }
 
    private static void solve(int cnt, int N, char[] word, int[] c) {
        if (cnt == N) {
            sb.append(word).append("\n"); // 이렇게 따로 해야지 word가 string으로 나옴. 아니면 주소로 출력됨~~
            return;
        }
        for (int i = 0; i < 26; i++) {
            if (c[i] == 0)
                continue;
            c[i]--;
            word[cnt] = (char) (i + 'a'); // 다시 int를 char로 변환
            solve(cnt + 1, N, word, c);
            c[i]++;
        }
    }
}