백준 애너그램 파이썬

 

6443번: 애너그램

백트래킹 문제로, 알파세 사전순으로 출력은 입력받을 때, sort를 적용하면 된다.

하지만 중복된 문자열은 출력 되면 안되기 때문에 이 조건에서 고민을 했던것 같다. 시간 초과가 나지 않으려면, 중복조건은 피해야하는데 어떻게 풀 수 있을까?

'aabc' 이 입력일 때, 

중복된 문자열을 피하려면, 재귀함수를 호출하며 가지가 뻗어나갈 때, 해당 depth에서 같은 문자가 가지에 포함되면 안된다. 하지만 주어진 문자열의 문자들을 다 사용해서 문자열을 만들어야하는 것이 목표다. 

이 생각으로부터 dictionary를 사용해서 현재 사용할 수 있는 각 알파벳의 개수를 +-1 을 해서 문자열을 만들어 나갈 수 있다.

dictionary를 사용하면 중복을 제거 할 수 있고, 각 알파벳에 대한 개수를 나타냄으로써 개수가 0보다 크면, 이어서 가지를 뻗어 나갈 수 있다.

def dfs(L,res):
    if L == len(arr):
        print(''.join(res))
        return
    for v in check:
        if check[v]:
            check[v] -= 1
            dfs(L+1,res+[v])
            check[v] += 1
        
            
n = int(input())
for _ in range(n):
    arr = list(input())
    arr.sort()
    check = {}
    for i in arr:
        if i not in check:
            check[i] = 1
        else:
            check[i] += 1
    dfs(0,[])

 

 

[baekjoon] 백준 6443번(파이썬): 애너그램