[백준] 6443번 : 애너그램 - C++ / JAVA

백준 6443 : 애너그램

등급 : Gold V

6443번: 애너그램 (acmicpc.net)

6443번: 애너그램

사용 알고리즘 : Backtracking

사용 자료구조 : -

 

문자열 중복을 방지하며 백트래킹을 하는 문제였다.

들어오는 알파벳을 계수 정렬(Counting Sort)로 처리해주고, 이를 검사해가면서 풀면 가능하게 된다.

( 방문 정보를 set으로 탐색하는 경우 TLE가 발생한다 )

---

  1. 알파벳을 계수 정렬 해주기 위해 크기가 26인 visit 배열 생성.

  2. 출력값으로 나올 char 배열 str을 생성.

  3. 백트래킹 함수 구현

     1) 본래 글자 사이즈와 동일해지면 출력.

     2) 계수 정렬해 둔 visit 배열을 탐색하며, 현재 위치에서 나올 수 있는 알파벳을 추출해가며 백트래킹 진행.

  4. 메인 함수에서 글자를 입력받고, 계수 정렬을 함.

  5. 백트래킹 실행 및 결과 출력.

---

<hide/>
#include <iostream>

using namespace std;

int visit[26] = { 0 };
char str[1001];
void dfs(string str, int x)
{
    if (x == str.size())
    {
        cout << str << "\n";
    }
    else
    {
        for (int i = 0; i < 26; i++)
        {
            if (visit[i] > 0)
            {
                visit[i]--;
                str[x] = i + 'a';
                dfs(str, x + 1);
                visit[i]++;
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    string x;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> x;
        for (int j = 0; j < x.size(); j++)
        {
            visit[x[j] - 'a']++;
        }
        dfs(x, 0);
        fill_n(visit, 26, 0);
    }
}

<hide/>
import java.io.*;
import java.util.*;

public class Main {
    static char[] str;
    static int[] visit = new int[26];
    static void dfs(int x, int len)
    {
        if(x==len)
        {
            System.out.println(str);
        }
        else
        {
            for(int i=0; i<26; i++)
            {
                if(visit[i] > 0)
                {
                    visit[i]--;
                    str[x] = (char)(i + 'a');
                    dfs(x+1, len);
                    visit[i]++;
                }
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        for(int i=0; i<n; i++)
        {
            String x = br.readLine();
            str = new char[x.length()];
            for(int j=0; j<x.length(); j++)
            {
                visit[x.charAt(j) - 'a']++;
            }
            dfs(0, x.length());
            Arrays.fill(visit, 0);
        }
    }
}