[백준] 6443번 애너그램

💡문제접근

• 전에 [N과 M 시리즈]를 통해서 공부했던 백트래킹 알고리즘을 이용해서 해결했다.
• 중복된 문자열을 출력하지 않는 과정에서 시간이 많이 걸렸던 문제였다. 백트래킹 문제가 나온다고해서 겁부터 먹는 습관을 조금씩 버리도록 노력하자.

💡코드(메모리 : 89112KB, 시간 : 688ms)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def recursive(idx, string):
    if idx == len(word):
        print(string)
        return
    else:
        for i in range(len(word)):
            if not visited[i]:
                temp = string + word[i]
                # 만약 문자열 temp가 ans에 없다면?
                if temp not in ans:
                    visited[i] = True
                    ans.add(temp)
                    recursive(idx+1, temp)
                    visited[i] = False
                # 문자열 temp가 ans에 있다면 → 중복된 문자열은 넣지 않아야하므로 X

N = int(input())
for _ in range(N):
    ans = set()
    word = list(input().strip())
    # 출력할 때에 알파벳 순서대로 출력하기 위해서 오름차순 정렬을 수행한다.
    word.sort()
    visited = [False] * len(word)
    recursive(0, '')

💡소요시간 : 41m