📃 문제
[BOJ] 애너그램 🔗링크
이 문제를 해결하려면, 애너그램에 대해서 먼저 알아야한다.
애너그램(Anagram)
단어 또는 구문의 글자를 재배열해서 만든 단어 또는 구문
글로 보면 무슨 말인지 모르겠으니 애너그램의 예시를 살펴보면,
EVERLAND(= LAVENDER), CINEMA(= ICEMAN), LE SSERAFIM(= I'M FEARLESS)
(르세라핌이 애너그램인줄 이번 기회에 알게 됐다,, 문찐)
아무튼 주어진 단어에서 배치만 바꾸어서 새로운 단어를 만드는게 애너그램이다.
다시 문제로 돌아가자면,
[입력]단어가 주어지고, [출력]주어진 단어를 이용한 모든 애너그램 단어를 만들어야 하는 문제이다.
🧠❓ 문제 접근 및 풀이
🐶 1번째 접근
입력 단어의 최대 길이는 20자, 출력 애너그램 개수는 100,000개 미만인 경우만 입력으로 주어진다는 조건 때문에 순열을 이용하면 될 듯 싶었다.
순열을 이용하면 각 글자의 배치를 바꿔 만들 수 있는 단어의 모든 경우의 수를 구할 수 있고,
여기서 Hash 자료구조(set 또는 dict)를 사용해 중복만 제거해주면 된다라고 생각했다.
다만 간과한 점이 하나 있었다.
100,000개 미만인 경우만 입력으로 주어진다 라는 문장만 보고
순열로 만들어지는 단어의 수도 100,000개 미만일 것이라고 생각했는데 이 점이 문제였다.
입력이 aa ... aa (a*20)으로 주어졌을때, 만들어지는 애너그램은 1개이지만,
순열로 만들어지는 단어의 수가 무려 20!(2e+18)으로 어마어마하게 크다.
당연히 시간 초과가 날게 뻔하니 이 방법은 패스..
순열을 이용해서 만든 코드를 테스트해보다가 알게 됐다 ㅎㅎ... 미리 시간복잡도 고려 안 한 내 잘못..
🐱 2번째 접근 (문제 해결)
입력이 aa ... aa으로 주어졌을때,
모든 자릿수의 글자는 동일한 글자이니 배치를 바꿔도 결국 동일한 단어가 나온다.
고등학교 때 배웠던 "같은 것이 있는 순열"으로 경우의 수를 구해야하 하는 것 같은데..
Python itertools 라이브러리엔 이런 경우의 수를 구하는 함수가 없었던 것 같아서 직접 구현했다.
DFS를 통해서 애너그램을 생성하였고
특정 자릿수에 글자를 배치할때 동일한 단어는 한번만 사용하도록 구현하였다.
아래는 풀이 코드이다.
우선 입력은 Counting Sort를 이용해 정렬 및 list에 입력받았고,
DFS를 통해서 애너그램을 생성하였다.
import sys
input = sys.stdin.readline
def dfs(word, anagram):
if len(anagram) == N_word:
print(''.join(map(lambda x : chr(x+97), anagram)))
return
for idx in range(26):
if word[idx] > 0:
word[idx] -= 1
anagram.append(idx)
dfs(word, anagram)
word[idx] += 1
anagram.pop()
N = int(input())
for _ in range(N):
input_word = input().strip()
word = [0] * 26
N_word = len(input_word)
for num in list(map(lambda x : x - 97, list(bytes(input_word, 'ascii')))):
word[num] += 1
dfs(word, [])
🐭 3번째 접근 (문제 해결)
위 풀이로도 풀이는 가능했지만, 최적화 할 수 있는 방법을 알아보다가
next permutation이라는 알고리즘을 알게 되었고, 이를 적용해서 풀어보았다.
import sys
input = sys.stdin.readline
def next_perm(w):
for i in range(len(w)-1, 0, -1):
if w[i-1] < w[i]:
for j in range(len(w)-1, i-1, -1):
if w[i-1] < w[j]:
w[i-1], w[j] = w[j], w[i-1]
return (w[:i] + sorted(w[i:]))
return False
N = int(input())
for _ in range(N):
w = sorted(input().strip())
while w:
print("".join(w))
w = next_perm(w)
