[백준] 6443 - 애너그램

1. 문제

6443번: 애너그램

2. 개요

N개의 문자열이 주어진다.

문자열로 만들 수 있는 애너그램을 사전순으로 출력하는 문제.

3. 풀이 및 코드

3-1. 풀이

문자열을 탐색하여 알파벳의 갯수를 배열로 저장하고 이 배열을 이용해 백트래킹으로 애너그램을 만든 후, 정렬하여 출력한다.

3-2. Python

import sys

def bt(idx = 0, s = ''):
    if idx == len(_s):
        analist.add(s)
        return

    for i in range(26):
        if alpha[i]:
            alpha[i] -= 1
            bt(idx + 1, s + chr(i + 97))
            alpha[i] += 1

N = int(sys.stdin.readline())

for _ in range(N):
    _s = sys.stdin.readline().rstrip()
    alpha = [0 for _ in range(26)]
    analist = set()

    for c in _s:
        alpha[ord(c) - 97] += 1

    bt()

    for ana in sorted(list(analist)):
        print(ana)

3-3. C#

using System.Text;

namespace boj_6443
{
    internal class Program
    {
        static int[] alpha = new int[26];
        static HashSet<string> anaset = new HashSet<string>();
        static string _s;
        
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());

            for (int i = 0; i < N; i++)
            {
                _s = Console.ReadLine();

                Array.Fill(alpha, 0);
                anaset.Clear();

                foreach (char c in _s)
                    alpha[c - 'a']++;

                bt(0, "");

                List<string> analist = anaset.ToList();
                analist.Sort();

                StringBuilder sb = new StringBuilder();
                foreach (string ana in analist)
                {
                    sb.Append(ana + "\n");
                }

                sb.Remove(sb.Length - 1, 1);

                Console.WriteLine(sb);
            }
        }

        static void bt(int idx, string s)
        {
            if (idx == _s.Length)
            {
                anaset.Add(s);
                return;
            }

            for (int i = 0; i < 26; i++)
            {
                if (alpha[i] > 0)
                {
                    alpha[i]--;
                    bt(idx + 1, s + (char)(i + 'a'));
                    alpha[i]++;
                }
            }
        }
    }
}

Console.WriteLine()가 너무 느려서 이를 이용해 하나씩 출력하면 시간초과가 발생한다.

StringBuilder를 이용해 모든 답들을 다 넣은 후, 마지막 개행문자만 삭제하고 한번에 출력한다.