[백준] 6443 - 팰린드롬 만들기 (JAVA)

[백준] 6443 - 팰린드롬 만들기

처음에는 문제를 읽고 '음.. 순열 문제군... 근데 중복되는 건 어떻게 제거하지?' 하다가 SortedSet에 넣어보기로 했었다. 결과는 역시나 예상대로 메모리 초과!
그래서 그 다음에는 순열을 돌 때 이전 인덱스와 문자가 같으면... 어떻게 어떻게 지지고 볶고... 해서 중복을 제거하면 되겠지!? 했는데, 중복되는 문자가 2개일 때는 먹히는데 늘어나면 안 먹히더라 ^_ㅜ
그렇다고 검사하는 범위가 늘어나면 또 메모리나 시간초과 날 것 같고...

결국 다른 사람들 풀이를 보고 힌트를 얻었는데, 문자 그 자체를 반복/조합해서 순열로 만드는 게 아니라 문자의 개수를 이용해서 중복없는 순열을 만드는 방법이 있었다.
심지어는 visited 배열도 불필요!

아래 Perm 메서드가 그걸 구현한 것인데, 알파벳의 개수를 기록한 int 배열 alphabet, 결과 문자를 담을 배열인 result, 현재 뽑은 문자를 카운트할 r, 뽑아야할 개수인 count(사실 result.length를 사용해도 된다.)를 인자로 사용한다.
그렇게 앞에서부터 alphabet배열을 돌면서 사용한 문자는 개수에서 빼주고, 재귀함수를 호출한 후 재귀함수에서 빠져나오면 다시 개수를 더해준다.

아래는 전체 소스코드이다.

import java.io.*;

// 6443 - 애나그램
public class Main {
    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));

        int N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            int[] alphabet = new int[26];
            String input = br.readLine();

            // 알파벳 개수 카운트
            for (int j = 0; j < input.length(); j++) {
                alphabet[input.charAt(j) - 'a']++;
            }

            char[] result = new char[input.length()];
            perm(alphabet, result, 0, input.length());

        }
        bw.close();
    }

    static void perm(int[] alphabet, char[] result, int r, int count) throws IOException {
        if (r == count) {
            bw.write(String.valueOf(result));
            bw.write("\n");
        }
        for (int i = 0; i < alphabet.length; i++) {
            if (alphabet[i] > 0) {
                alphabet[i]--;
                result[r] = (char)( i+'a');
                perm(alphabet, result, r+1, count);
                alphabet[i]++;
            }
        }
    }
}