문제 탐색하기

입력 자료 정리

1. n은 들어올 단어의 개수로, 이 문제에서는 테스트 케이스 역할이다
2. 이어서 들어오는 문자열은 탐색할 문자 집합이다

해결방법 추론

1. 간단하게 백트래킹으로 원하는 결과를 얻을 수 있다고 생각하였다
2. 중복을 제거하고 정렬을 하기 위해 TreeSet 자료구조를 사용하였다
3. 백트래킹으로 가능한 모든 경우를 TreeSet에 넣고 출력하면 될 것이다
4. 한가지 주의할점은 방문배열을 만들어야한다. 같은 단어가 여러번 만들어지면
   분명 재귀함수가 터질 것이기 때문이다
5. 재귀함수의 등장으로 사실상 Set 자료구조는 의미가 없으나 TreeSet은 추가 정렬없이
   자동으로 정렬되므로 그냥 사용하기로 결정하였다

시간복잡도 계산하기

1. 시간복잡도는 n!이다. 이때 n은 문자열의 길이이며 최대 20이므로 20!이 될것이다
2. 시간복잡도를 계산했을 때, 절대 백트래킹을 사용할 수 없음을 알 수 있다
3. 하지만 문제에서 연산이 10만 이하라고 적어놨기에 백트래킹으로 해결할 수 있다
4. 따라서 시간복잡도 자체는 O(|S|!)이며, 최대 연산 10만 제한으로 문제를 해결할 수 있다

코드 설계하기

입력값 상태 관리하기

1. n은 변수로 관리하며 입력 문자열은 문자 배열로 받아 관리한다
2. 방문 체크를 위한 별도의 boolean 배열을 하나 만들고 TreeSet도 하나 만들어둔다

백트래킹 설계

함수식

- backtrakcing(int length, int depth, String s)
1. base condition을 위한 length와 탐색을 위한 depth를 파라미터로 두었으며,
문자열을 누적해서 만들어가기 위해 문자열 s를 파라미터로 두었따

재귀식

- backtracking(length, depth+1, s + arr[i])
1. 전형적인 백트래킹 재귀식이다

base condition

- if(depth == length){...}
깊이와 길이가 같아질 때, set에 완성 문자열을 넣어주고 종료한다

출력값 설계

1. 완성한 Set의 값들을 출력하면 정답이 될텐데..

시도회차 수정

1회차 시도 실패..

1. 25%에서 메모리초과로 실패해버렸다

원인 분석 및 변경

1. 문제의 원인을 분석해보니, 문자열의 길이만큼 방문 배열을 선언해주는 것이 문제였다
2. 문자열의 길이는 20이니까 20!만큼의 연산이 있으면서 그만큼 탐색하는 배열의 크기도 커진다
3. 따라서 알파벳의 개수 정보를 담는 26개의 배열로 바꿔줄 필요가 있다
4. int배열로 26개의 고정 크기를 가지며, 각 문자의 인덱스의 값을 증가시켜준다
5. 또한 백트래킹에서는 0보다 큰 경우 값을 줄이고, 백트래킹 진행하며 이후 다시 증가시킨다
6. 문자열은 그대로 유지해도 되는데 (char)타입으로 (i-'a')를 하는 별도의 작업을 해주면 된다

2회차 시도 성공

1. 이렇게 변경하였을 때, 메모리 초과 없이 문제가 해결된다!

정답 코드

(1회차 실패)

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


public class Main {
    static boolean[] alpha;
    static Set<String> set;
    static char[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            arr = br.readLine().toCharArray();
            alpha = new boolean[arr.length];
            set = new TreeSet<>();
            backtracking(arr.length, 0, "");
            for (String s : set) {
                bw.write(s+"\n");
            }
        }


        br.close();
        bw.close();
    }

    private static void backtracking(int length, int depth, String s) {
        if(depth == length){
            set.add(s);
            return;
        }


        for (int i = 0; i < length; i++) {
            if(!alpha[i]){
                alpha[i] = true;
                backtracking(length, depth+1, s+arr[i]);
                alpha[i] = false;
            }
        }
    }
}

(2회차 성공!)

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


public class Main {
    static int[] alpha;
    static Set<String> set;
    static char[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            arr = br.readLine().toCharArray();
            alpha = new int[26];
            for (int j = 0; j < arr.length; j++) {
                alpha[arr[j] - 'a']++;
            }

            set = new TreeSet<>();
            backtracking(arr.length, 0, "");
            for (String s : set) {
                bw.write(s+"\n");
            }
        }


        br.close();
        bw.close();
    }

    private static void backtracking(int length, int depth, String s) {
        if(depth == length){
            set.add(s);
            return;
        }


        for (int i = 0; i < 26; i++) {
            if(alpha[i] > 0){
                alpha[i]--;
                backtracking(length, depth+1, s+((char)(i+'a')));
                alpha[i]++;
            }
        }
    }
}

문제 링크

6443번 - 애너그램