[Python/파이썬] 백준 6443번 애너그램

6443번: 애너그램

 

문제

씬디는 애너그램(anagram) 프로그램을 만들어 줄 수 있는 남자를 좋아한다. 참고로 씬디는 매우 예쁘다.

애너그램 프로그램이란, 입력받은 영단어의 철자들로 만들 수 있는 모든 단어를 출력하는 것이다. 가령 "abc" 를 입력받았다면, "abc", "acb", "bac", "bca", "cab", "cba" 를 출력해야 한다.

입력받은 단어내에 몇몇 철자가 중복될 수 있다. 이 경우 같은 단어가 여러 번 만들어 질 수 있는데, 한 번만 출력해야 한다. 또한 출력할 때에 알파벳 순서로 출력해야 한다.

입력

첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다. 영단어는 소문자로 이루어져 있다. 단어의 길이는 20보다 작거나 같고, 애너그램의 수가 100,000개 이하인 단어만 입력으로 주어진다.

출력

각각의 영단어마다 모든 가능한 애너그램을 출력한다. 각각의 영단어에 대한 애너그램을 출력할 때, 알파벳 순서로 중복되지 않게 출력한다.

코드

from collections import defaultdict
import sys
input = sys.stdin.readline


def bt(w, length):
    if len(w) == length:
        print("".join(w))
        return
    for a in alphabet:
        if alphabet[a]:
            alphabet[a] -= 1
            bt(w+a, length)
            alphabet[a] += 1


for _ in range(int(input())):
    word = sorted(list(input().strip()))
    alphabet = defaultdict(int)
    for w in word:
        alphabet[w] += 1
    bt('', len(word))

 

처음에는 permutations 사용했는데 예상을 벗어나지 않고 시간 초과가 발생했다. 그래서 백트래킹을 이용하여 구현하였다.

입력받은 word에 있는 알파벳들의 개수를 센 딕셔너리 alphabet이 있다. bt함수에서는 alphabet의 키에 대해 for문을 돌며 alphabet[a] > 0이라면 아직 사용할 수 있는 알파벳이므로 alphabet[a]의 값을 1 감소시켜서 사용했다고 표시를 해주고 bt(w+a, length)를 재귀호출한다.만약 w의 길이가 입력받은 word의 길이(length)와 같아진다면 프린트해주고 리턴한다.

 

원래 alphabet에 저장된 알파벳의 개수가 0이 되면 alphabet에서 del시켜버리도록 했는데 이렇게 하니 for문을 돌던 도중 iterator인 alphabet의 원소에 변화가 생겨서 오류가 발생했다. 이전에도 몇 번 발생시킨적 있는 오류인데 앞으로는 더 조심해야겠다.