[백준/Python] 6443번 에너그램

문제

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

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

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

입력

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

 

 

틀린 풀이(시간초과)

import sys
si = sys.stdin.readline
N = int(si())

def dfs(current, li: list):

    if current == len(input):
        word_set.add("".join(li))
        return
    
    for i in range(len(input)):
        if visited[i] == 0:
            li.append(input[i]) # 추가
            visited[i] = 1 # 방문처리
            dfs(current + 1, li)
            li.pop() # 초기화
            visited[i] = 0 # 초기화

    return

for i in range(N):
    word_list = list()
    word_set = set() 

    input = list(map(str, si().rstrip()))
    input.sort()
    visited = [0 for _ in range(len(input))]

    dfs(0, [])
    word_list = list(word_set)
    word_list.sort()

    for word in word_list:
        print(word)

 

 

정답 풀이

# 애너그램
# 복습 횟수:1, 00:30:00, 복습필요O
import sys
si = sys.stdin.readline
N = int(si())

def dfs(enegram_dict, answer: list):

    if len(answer) == len(c_list):
        print("".join(answer))
        return
    
    for enegram in enegram_dict:
        if enegram_dict[enegram]:
            enegram_dict[enegram] -= 1
            answer.append(enegram)
            dfs(enegram_dict, answer)
            enegram_dict[enegram] += 1
            answer.pop()
    return

for i in range(N):
    c_list = list(map(str, si().rstrip()))
    c_list.sort()
    enegram_dict = dict()
    for c in c_list:
        if c in enegram_dict.keys():
            enegram_dict[c] += 1
        else:
            enegram_dict[c] =  1
    
    dfs(enegram_dict, [])

 

 

두 풀이의 차이점

1. 첫번째 풀이는 예를 들어 a b c a 인 경우 첫번째 a를 기준으로 dfs 탐색, 마지막 a를 기준으로 탐색하는 경우가 있다. 하지만 이는 같은 a이므로 중복된다. 이런 점에서 비효율성이 나타나 dfs 탐색의 깊이가 더 커진다. 하지만 두번째 풀이의 경우 dict을 활용해 위와 같은 중복을 해결하였으므로 효율적이다.

2. 첫번째 풀이에선 set()을 통해 새로운 자료구조를 만드는 과정에서 비효율성이 나타난다. 에너그램이 100,000개까지 만들어질 수 있는 입력이 주어질 수 있는데 set을 만들면서 꽤 오랜 시간이 걸릴 수 있다.