[백준] 애너그램 6442 java - 백트래킹

 

전형적인 백트래킹 문제이다.

다만 각 순열의 결과를 자료구조에 저장하게 된다면 메모리 초과가 발생한다.

맨 처음 정렬된 상태로 순열의 결과를 저장하려고 TreeSet 자료구조를 선택해서

메모리 초과가 났다 ㅜㅜ 순열 결과를 저장하지 않고

바로 sb에 담아서 출력하는 방식으로 수정해서 해결했다!

 

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

 

첫번째 풀이

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

public class Main {
    static String words;
    static boolean[] visited;
    static HashSet<String> answer = new HashSet<>();
    static void backtraking(String result, int depth, int length){
        if(depth==length){
            answer.add(result);
            return;
        }

        for(int i=0;i<length;i++){
            if(!visited[i]){
                visited[i] = true;
                backtraking(result+words.charAt(i),depth+1,length);
                visited[i] = false;
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        for(int i=0;i<N;i++){
            words = br.readLine();
            char[] charArray = words.toCharArray();
            Arrays.sort(charArray);
            words = new String(charArray);
            visited = new boolean[words.length()];
            backtraking("",0,words.length());
        }

        for(String word:answer){
            System.out.println(word);
        }
    }
}

TreeSet에 결과를 저장한다면

P가 최대 100,000이고 L≤20인 경우

최악의 경우 메모리 초과 발생!

 

 

두번째 풀이(답)

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

public class Main {
    static String words;
    static int[] check;
    static StringBuilder sb;

    static void backtracking(String result, int depth, int length) {
        if (depth == length) {
            sb.append(result).append("\n");
            return;
        }
        for (int i = 0; i < 26; i++) {
            if (check[i]>0) {
                check[i]--;
                backtracking(result + (char)(i+'a'), depth + 1, length);
                check[i]++;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        check = new int[26];

        for (int i = 0; i < N; i++) {
            words = br.readLine();
            char[] charArray = words.toCharArray();
            for(int j=0;j<charArray.length;j++){
                check[charArray[j]-'a']++;
            }
            words = new String(charArray);
            backtracking("", 0, words.length());
            for(int j=0;j<26;j++){
                check[j]=0;
            }
        }

        System.out.println(sb);
    }
}

check 배열에 입력 문자의 개수를 담아서

출력할때마다 하나씩 빼주는 방식으로 중복 처리했다!!