백준 6443[자바] java 애너그램

문제 링크: https://www.acmicpc.net/problem/6443

6443번: 애너그램

▶문제

씬디는 애너그램(anagram) 프로그램을 만들어 줄 수 있는 남자를 좋아한다. 참고로 씬디는 매우 예쁘다.

애너그램 프로그램이란, 입력받은 영단어의 철자들로 만들 수 있는 모든 단어를 출력하는 것이다. 가령 "abc"를 입력받았다면, "abc", "acb", "bac", "bca", "cab", "cba"를 출력해야 한다.

입력받은 단어내에 몇몇 철자가 중복될 수 있다. 이 경우 같은 단어가 여러 번 만들어질 수 있는데, 한 번만 출력해야 한다.  또한 출력할 때에 알파벳 순서로 출력해야 한다.

▶입력

첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다. 영단어는 소문자로 이루어져 있다. 단어의 길이는 20보다 작거나 같고, 애너그램의 수가 100,000개 이하인 단어만 입력으로 주어진다.

▶출력

N개의 영단어에 대한 모든 가능한 애너그램을 출력한다. 각각의 영단어에 대한 애너그램을 출력할 때, 알파벳 순서로 중복되지 않게 출력한다.

▶해설

단순한 백트래킹 문제입니다. 조건을 먼저 살펴보겠습니다. 

 

1. 문자열 순서대로 조합해서 출력

2. 중복되는 문자열은 출력하지 않음

 

문자열을 정렬하고 이전에 완성된 문자열은 출력하지 않도록 해서 백트래킹으로 풀었는데 메모리 초과가 발생했습니다. 따라서 다른 방법으로 중복을 제거할 필요가 있었습니다. 

 

기존에는 문자열의 인덱스를 방문 처리 했습니다. 문자열의 인덱스가 아닌 알파벳을 방문 처리하는 방식으로 접근했습니다. 즉 aabbcc일 때

 

기존 방문 체크-> 0(방문) -> 1(방문) -> ~~~ 다시 돌아와서 1(방문) -> 0(방문) -> ~~ 처음부터 다시 방문해서 중복이 발생합니다. 

 

알파벳 방문 체크 -> a(방문)-> a(방문)-> b(방문) -> ~~~~ 다시 돌아와서 두 번째 a가 아닌 b부터 방문해서 중복을 처리할 수 있었습니다.  

 

이제 방문한 것을 담기 위해서 Stack을 활용합니다. 최종적으로 Stack의 것들을 순회하면서 우선순위 큐에 넣고 마지막에 출력합니다.

private static void dfs(char [] s, int limit) {
    if(limit== stack.size()){
        StringBuilder sb = new StringBuilder();
        for(char now: stack){
            sb.append(now);
        }
        queue.add(sb.toString());
    }

    for(int i=0; i<26; i++){
        if(check[i]>0){
            check[i]--;
            stack.push((char)(i+'a'));
            dfs(s,limit);
            stack.pop();
            check[i]++;
        }
    }
}

 

전체 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Collectors;


public class Main {

    static int n;
    static int[] check;
    static Stack<Character> stack =new Stack<>();
    static PriorityQueue<String> queue = new PriorityQueue<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<n; i++){
            char[] chars = br.readLine().toCharArray();
            int length = chars.length;
            check = new int[26];
            for(char now: chars){
                check[now-'a']++;
            }
            dfs(chars,length);
            while(!queue.isEmpty()){
                sb.append(queue.poll()).append("\n");
            }
        }
        System.out.println(sb.toString());
    }

    private static void dfs(char [] s, int limit) {
        if(limit== stack.size()){
            StringBuilder sb = new StringBuilder();
            for(char now: stack){
                sb.append(now);
            }
            queue.add(sb.toString());
        }

        for(int i=0; i<26; i++){
            if(check[i]>0){
                check[i]--;
                stack.push((char)(i+'a'));
                dfs(s,limit);
                stack.pop();
                check[i]++;
            }
        }
    }
}