[BOJ] 백준 6443번 애너그램 (Java)

#6443 애너그램

난이도 :  골드 5

유형 : 문자열 / 순열

6443번: 애너그램

▸ 문제

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

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

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

▸ 입력

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

▸ 출력

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

 

문제 풀이  

기본적인 순열문제이다. 서로 다른 n개중 r개를 골라 순서를 고려해 나열한 경우의 수이다. 원래 브루트포스탐색이라 n!이 걸리는데 문제에서는 최대 100,000개만 생성되도록 테케를 제한해주었다.

그리고 그냥 재귀를 통해 풀이를 하면 메모리초과가 발생한다. 재귀가 쌓이면서 메모리가 터졌다. 문제에서  순열 갯수가 100,000개인 문자열만 주어진다고 했으니 아마 예로 'aaaaabbbbbbcccc'처럼 중복된 문자가 많은 문자열들만 주어졌던 것 같다. 그래서 만약 그대로 탐색하게 되면 15*15*15*···로 재귀가 쌓이게 되지만 중복을 제거하고 탐색해주면 3*3*3*···로 줄여줄 수 있다.

// 메모리 초과
arr = br.readLine().toCharArray();
check = new boolean[arr.length];

// 통과
arr = br.readLine().toCharArray();
check = new int[26];
for(char c : arr) {
    check[c-'a']++;
}

 

풀이 코드 

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

public class Main {

	static char[] arr;
	static int[] check;
	static StringBuilder sb;
	static Stack<Character> s;
	static Set<String> set;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringBuilder result = new StringBuilder();
		int n = Integer.parseInt(br.readLine());
		while(n-- > 0) {
			set = new TreeSet<>();
			arr = br.readLine().toCharArray();
			check = new int[26];
			for(char c : arr) {
				check[c-'a']++;
			}
			s = new Stack<>();
			comb(arr.length);
			set.stream().forEach(s -> result.append(s).append("\n"));
		}
		System.out.println(result.toString());
	}
	
	static void comb(int r) {
		if(r == s.size()) {
			StringBuilder sb = new StringBuilder();
			for(char c : s) {
				sb.append(c);
			}
			set.add(sb.toString());
		}
		
		for(int i=0; i<26; i++){
			if(check[i] > 0) {
				check[i]--;
				s.push((char)(i+'a'));
				comb(r);
				s.pop();
				check[i]++;
			}
		}
	}
}