[백준] 6443 애너그램 (Python 파이썬 풀이)

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

6443번: 애너그램

1. dfs로 백트래킹을 구현하여 가능한 모든 알파벳 조합을 뽑아주었다

result 리스트에 만들어지는 단어들을 모두 append해주고, result를 sort해주었더니.. 메모리 초과가 났다. 
최근에 코테를 2번정도 봤는데, 단순하게 구현을 해주면 쉽게 풀리지만 시간복잡도와 공간복잡도, 혹은 edge case에서 틀렸거나 비효율적인 코드로 제출해서 털렸던 기억이있다.. 
이런걸 학습하기에 6443번은 딱 좋은 문제인 것 같다. 

n = int(input())

def dfs(temp, length, visited):
    if len(temp) == length:
        result.append(temp)
        return
    for i in range(length):
        if not visited[i]:
            visited[i] = True
            dfs(temp+data[i], length, visited)
            visited[i] = False

for _ in range(n):
    data = list(input())
    length = len(data)
    result = []
    visited = [False] * length
    for i in range(length):
        visited[i] = True
        dfs(data[i], length, visited)

    result.sort() # O(NlogN)
    for word in result:
        print(word)
# 메모리 초과

 

2. 메모리 초과해결하기..

- 재귀 탈출 조건을 확인하기 
- 변수를 메모리에 저장할 일을 줄이기 (공간 복잡도 줄이기)

그래서 dfs함수에서 단어조합 생성이 끝난 경우 , 즉 len(temp) == length 로 재귀탈출을 하는 경우에 바로 출력을 해주어서 result 공간을 사용하지 않는 방법으로 해결했다. 
이렇게 하려면 사용할 알파벳은 미리 정렬해두어야 하므로, 최종 결과값 result를 sort하는 대신 입력된 단어를 리스트에 넣고 이를 사전순 정렬했다. 

ex) acb -> ['a', 'b', 'c']

data = sorted(list(input().strip())) # 사전순 정렬

 

통과 코드 

import sys
from collections import defaultdict
input = sys.stdin.readline
n = int(input())

def dfs(temp, length, visited):
    if len(temp) == length:
        print(temp)
        return
    for i in visited: # 알파벳
        if visited[i]:
            visited[i] -= 1
            dfs(temp+i, length, visited)
            visited[i] += 1

for _ in range(n):
    data = sorted(list(input().strip())) # 사전순 정렬
    length = len(data)
    visited = defaultdict(int) # 등장하는 알파벳 세어주기
    for i in range(length):
        visited[data[i]] += 1
    dfs("", length, visited)