🔴 문제 개요
🚀 난이도 : GOLD 5
주어지는 영단어마다 모든 가능한 애너그램을 출력해야 합니다. 각각의 영단어에 대한 애너그램을 출력할 때, 알파벳 순서로 중복되지 않게 출력해야 합니다.
애너그램이란 어떤 영단어를 이루는 철자들의 순서를 바꿔 만들어 낼 수 있는 모든 단어를 뜻합니다.
예를 들어 abc의 에너그램은 acb, bac, bca 등이 있을 수 있습니다.
제한 사항
- 첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다.
- 영단어는 소문자로 이루어져 있다.
- 단어의 길이는 20보다 작거나 같고, 애너그램의 수가 100,000개 이하인 단어만 입력으로 주어진다.
🟠 Solution
기본적인 백트래킹 문제라고 생각할 수 있습니다. 주어지는 단어의 알파벳으로 조합할 수 있는 모든 단어를 출력하면 되니까요. 심지어 알파벳 순서대로 출력해야 하니 정렬 후, dfs 탐색을 수행하면 쉽게 정답을 도출해낼 수 있을 것 같습니다.
import sys
input = sys.stdin.readline
N = int(input().rstrip())
def dfs(idx: int, word: str) -> None:
# 재귀 탈출 조건
if idx == len(st):
# 중복 x
if word not in word_set:
print(word)
word_set.add(word)
return
# 재귀
for i in range(len(st)):
if not included[i]:
# 백트래킹
included[i] = True
dfs(idx + 1, word + st[i])
included[i] = False
for _ in range(N):
st = list(input().rstrip())
st.sort() # 알파벳 순서대로 탐색을 위함
included = [False for _ in range(len(st))]
word_set = set()
dfs(0, "")
알파벳 순서대로 조합하기 위해 dfs 전 정렬을 수행했고, 두 개 이상의 철자를 가진 알파벳 조합에 대해 고려해주기 위해 별도의 set을 정의해서 활용했습니다. 전형적인 백트래킹 풀이입니다.
하지만 이 문제에서 이런 방식으로 풀이한다면 시간초과가 발생합니다. 바로 중복되는 철자에 의해서 중복되는 불필요한 재귀가 이루어지기 때문입니다. 또한, 100,000개의 애너그램이 발생할 수 있는 input에 대해 set 연산의 오버헤드도 영향을 줄 수 있을 것 같습니다.
이를 어떻게 해결해야 할까요? 중복되는 철자를 더욱 효율적으로 고려한 백트래킹을 위해서 dictionary를 활용할 수 있습니다. dictionary의 키로 알파벳 철자, 값으로 철자가 등장하는 횟수를 관리해준다면, 백트래킹 과정에서 이 값을 줄여가면서 탐색을 수행할 수 있습니다. dictionary를 탐색 시에는 알파벳 순서대로 이루어질 수 있어서 중복되는 재귀를 발생하지 않도록 할 수 있습니다. 이를 위해서는 당연히 dictionary에 키, 값을 삽입하기 전 알파벳순으로 입력하기 위해 정렬을 해줘야합니다.
import sys
from typing import Dict
input = sys.stdin.readline
N = int(input().rstrip())
def dfs(st_dict: Dict[str, int], answer: str) -> None:
"""
알파벳 순서대로, 알파벳 등장 횟수에 따라 딕셔너리를 활용해 백트래킹을 수행합니다.
"""
# 재귀 종료 조건
if len(answer) == len(st):
print(answer)
return
# 재귀
for s in st_dict:
if st_dict[s]:
# 백트래킹
st_dict[s] -= 1
dfs(st_dict, answer + s)
st_dict[s] += 1
for _ in range(N):
st = list(input().rstrip())
st.sort() # dictionary에 알파벳 순서대로 담기 위함
st_dict = {}
# dictionary에 알파벳 등장 횟수 담기
for s in st:
if s in st_dict:
st_dict[s] += 1
else:
st_dict[s] = 1
dfs(st_dict, "")또한, 자체적으로 최종 애너그램에 대한 중복도 고려해주기 때문에 set 연산을 별도로 수행하지도 않습니다. 이 문제와 같이 특정 값이 여러 번 등장할 수 있는 백트래킹, dfs 과정에서 dictionary를 효율적으로 활용할 수 있다는 점 기억해두면 좋을 것 같습니다. 이를 깨닫게 해준 좋은 문제였다고 생각합니다.
🙏 문제 접근 방법 및 코드에 대한 피드백과 질문은 환영입니다!
