[백준] 6643번_애너그램_Java

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

👀 문제 접근

---

영단어 철자로 단어 출력

애너그램 프로그램이란, 입력받은 영단어의 철자들로 만들 수 있는 모든 단어를 출력하는 것이다.

예를 들어 “abc”로 만들 수 있는 철자들은 "abc", "acb", "bac", "bca", "cab", "cba”이다.

입력 받은 단어내에 철자가 중복될 수 있으며, 이 경우 같은 단어가 여러번 만들어 질 수 있다. 따라서 중복되는 단어들은 한 번만 출력될 수 있도록 해야한다.

🔎 해결 방식

---

입력

• 입력할 단어의 개수 n 을 입력한다.
• 단어 input 을 입력한다.

단어 조합하기

• 백트래킹을 통해 단어를 조합한다.
• input 을 순회하며 단어 조합을 시도한다.
  • visited 를 통해 이미 조합에 포함 시킨 알파벳인지 확인한다.
  • 조합된 단어가 이미 출력된 단어인지 set 을 통해 확인한다.
  • 알파벳이 포함돼 있지 않고, 이미 출력되지 않았을 때 visited[i] 를 true로, 조합중인 단어를 저장하는 arr[depth] 에 input[i] 를 저장한 뒤, dfs 를 호출한다.
• depth 가 input 배열의 길이와 같아졌을 때 결과를 출력하고, 중복 출력될 수 없도록 set 에 출력한 단어를 포함시킨다.

💻 구현 코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Main {
    public static char[] input;
    public static boolean[] visited;

    public static void dfs(char[] arr, int depth, Set<String> set) {
		
        //char형을 String으로 변환
        String curr = new String(arr);

		// 탐색이 종료되면 결과 print 및 set에 단어 추가
        if (depth == input.length) {
            System.out.println(arr);
            set.add(curr);
            return;
        }
        
        for (int i = 0; i < input.length; i++) {
        	// 만들어진 단어가 이미 한 번 만들어진 단어인지 체크
            if (!visited[i] && !set.contains(curr)) {
                visited[i] = true;
                arr[depth] = input[i];
                dfs(arr, depth + 1, set);
                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++) {
            input = br.readLine().toCharArray();
            Arrays.sort(input);
            visited = new boolean[input.length];

            dfs(new char[input.length], 0, new HashSet<>());
        }
    }
}

✨ 마무리

---

해결 방법에 대한 아이디어는 금방 떠올랐다. 기존 백트래킹 방식에서 조합된 단어가 중복되지 않게 하는 방법만 알아내면 됐다.

Set을 활용하여 해당 문제를 해결하려 했고, 처음 구현을 완료했을 때는 단어 중복 여부 체크를 탐색이 다 끝난 후에 체크하도록 하였다.

이렇게 제출하니 메모리 초과 문제가 발생했고, 이를 해결하기 위해 단어 조합 과정에서 중복 여부 체크를 하도록 하니 정답으로 인정될 수 있었다.

골드 레벨인거 치고는 그렇게 깊이 고민하지 않아도 되는 문제였다.