[백준 6443] 애너그램 (Gold 5)

문제

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

접근

• 완전 탐색으로 구현
  • 먼저 인풋으로 들어오는 일파벳을 딕셔너리에 넣는다.
  • 그 이후 순열을 재귀함수로 구현한다. 이 때 재귀를 타는 조건은 딕셔너리에 해당 알파벳이 존재하면 재귀를 태운다.
  • permutation을 사용해 모든 경우의 수를 구할 경우 TLE가 발생한다.

Code

import sys
from collections import defaultdict


def go(cnt):
    if cnt == len(st):
        print("".join(ans))
        return

    for i in range(ord('a'), ord('z') + 1):
        curr_alpha = chr(i)
        if alpha_dict[curr_alpha]:
            alpha_dict[curr_alpha] -= 1
            ans.append(curr_alpha)
            go(cnt + 1)
            alpha_dict[curr_alpha] += 1
            ans.pop()


n = int(sys.stdin.readline())
for _ in range(n):
    alpha_dict = defaultdict(int)
    ans = []
    st = list(map(str, sys.stdin.readline().strip()))
    for s in st:
        alpha_dict[s] += 1
    go(0)