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

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

 

문제 풀이 1 (오답)

문제에서 단어의 길이는 20보다 작고, 애너그램의 수가 100,000개 이하라고 했다.

그래서 단순한 완전 탐색 문제라고 생각을 했고 입력 받은 문자열을 순열로 돌려 Set에 넣어 중복을 제거했다.

하지만 메모리 초과가 발생했다.

 

100,000개 이하라고해서 메모리 초과가 발생하지 않을것이라고 생각했다.

하지만 aaaabbbbbbbccccccc 와 같이 중복이 많은 문자열이 입력으로 들어온다면 애너그램의 수는 적지만 메모리는 터질것이다.

 

문제 풀이 2 (prev 사용)

따라서 중복을 해결하기 위해 prev 변수를 사용해서 중복된 문자 처리를 건너뛰었다. 

public static void dfs(int depth) {
    if (depth == str.length()) {
        list.add(String.valueOf(selected));
        return;
    }

    char prev = '0';
    for (int i = 0; i < str.length(); i++) {
        if (visited[i] || chars[i] == prev)
            continue;
        visited[i] = true;
        selected[depth] = chars[i];
        prev = chars[i];
        dfs(depth + 1);
        visited[i] = false;
    }
}

 

 

기존 DFS 순열 코드에서 chars[i] == prev 조건을 추가해 중복된 문자의 처리를 방지했다.

같은 depth에서 이전에 선택했던 문자와 동일한 문자가 다시 선택되는 것을 막으면, 중복된 애너그램을 생성하지 않게 된다.

예를 들어, 문자열이 "AAB"인 경우를 생각해보자

 

초기 상태

• 입력: chars = ['A', 'A', 'B']
• 초기 값: visited = [false, false, false], selected = [], depth = 0

첫 번째 호출: dfs(0)

• 루프 반복 (depth = 0):
  • i = 0: 첫 번째 'A' 선택 →  visited = [true, false, false], selected = ['A'], prev = 'A'
    • 재귀 호출: dfs(1)
    • 여기서 dfs를 들어가면 char prev = '0';로 인해 prev가 '0'으로 초기화 된다.
  • i = 1: chars[1] == prev → 건너뜀. ( chars[1] 와 prev 모두 'A')
  • i = 2: 'B' 선택 →  visited = [ false, false, true], selected = ['B'], prev = 'B'

prev는 DFS의  같은 depth에서만 중복을 방지한다.

다음 depth로 들어가면 char prev = '0';로 인해 prev가 초기화 된다.

즉, 현재 같은 depth에서만 prev를 통해 중복을 방지한다.

 

처음에는 prev를 사용해 값을 비교하면, "AAB"와 같은 경우에서 첫 번째 'A'와 두 번째 'A'가 같기 때문에 제외될 것이라고 생각했지만
prev는 같은 깊이(depth) 내에서 중복을 확인하고 건너뛰는 역할만 하기 때문에, 다음 깊이에서는 다시 동일한 문자를 선택할 수 있어 문제가 없다.

 

전체 코드

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

public class Main {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static StringTokenizer token;

	static String str;
	static char[] chars, selected;
	static boolean[] visited;

	static List<String> list;

	public static void dfs(int depth) {
		if (depth == str.length()) {
			list.add(String.valueOf(selected));
			return;
		}

		char prev = '0';
		for (int i = 0; i < str.length(); i++) {
			if (visited[i] || chars[i] == prev)
				continue;
			visited[i] = true;
			selected[depth] = chars[i];
			prev = chars[i];
			dfs(depth + 1);
			visited[i] = false;
		}

	}

	public static void init() throws Exception {
		list = new ArrayList<>();
		str = input.readLine();
		chars = new char[str.length()];
		selected = new char[str.length()];
		visited = new boolean[str.length()];
		for (int i = 0; i < str.length(); i++) {
			chars[i] = str.charAt(i);
		}
		Arrays.sort(chars);
	}

	public static void main(String[] args) throws Exception {
		int T = Integer.parseInt(input.readLine());
		for (int t = 0; t < T; t++) {
			init();
			dfs(0);
			for (String str : list) {
				output.append(str).append("\n");
			}
		}
		System.out.println(output);
	}
}