[백준/파이썬] #6443

접근은 맞았다고 생각했는데 시간초과가 났다. defaultdict을 통해 set()을 순회하는 경우를 방지했고, itertools 라이브러리를 사용했기에 어디서 시간초과가 났는지 감이 잡히지 않아 풀이를 참고했다. 

import sys
from collections import defaultdict
from itertools import permutations

input = sys.stdin.readline

N = int(input())
word_list = []
for _ in range(N):
    word = ''.join(sorted(input().replace("\n", "")))
    word_list.append(word)

anagrams = []
anagrams_dict = defaultdict(lambda:0)
for word in word_list:
    for word_case in permutations(list(word), len(word)):
        word_string = ''.join(word_case)
        if anagrams_dict[word_string] == 0:
            anagrams.append(word_string)
            anagrams_dict[word_string] = 1

print('\n'.join(anagrams))

 

해당 문제는 전형적인 백트래킹 문제라고 한다. 다만 고려해야 하는 점은 중복된 철자로 인해 불필요한 탐색이 발생할 수 있고, 이 경우를 없애 줘야 한다는 점이다. 가능한 모든 경우를 탐색하기 위해서 재귀 함수를 사용하였다. 

import sys

input = sys.stdin.readline

N = int(input())
word_list = []
for _ in range(N):
    word = ''.join(sorted(input().replace("\n", "")))
    word_list.append(word)


def dfs(string_dict, current_string):
    if len(current_string) == len(word):
        print(current_string)
        return
    
    for string in string_dict:
        if string_dict[string]:
            string_dict[string] -= 1
            dfs(string_dict, current_string + string)
            string_dict[string] += 1


anagrams = []
anagrams_dict = dict()
for word in word_list:
    anagrams_dict = dict()
    for string in word:
        if string in anagrams_dict:
            anagrams_dict[string] += 1
        else:
            anagrams_dict[string] = 1

    dfs(anagrams_dict, "")