[백준OJ] 6443번 애너그램

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

6443번: 애너그램

---

 

풀이

길이가 최대 20인 문자열이므로, N값이 작기때문에 백트래킹을 이용하여 모든 경우의 수를 구해주면 된다. 이때 알파벳순으로 출력을 해야하므로, 전부다 구한뒤, 중복을 제거하고 정렬을 하는것과 맵에 INSERT해서 출력을 하는것보단,

입력받은 문자열을 구성하는 알파벳들의 개수를 모두 세어준뒤, 알파벳 순서대로 존재하면 추가하고 다음으로 넘어가주는 백트래킹을 이용하면 정렬없이 알파벳 순서대로 출력이 가능해진다.

 

코드

#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<algorithm>
using namespace std;

int n;
int visited[26] = { 0 };
string str;
string answer;

void dfs(int index,int size) {
	if (index == size) {
		cout << answer << "\n";
		return;
	}
	for (int i = 0; i < 26; i++) {
		if (visited[i]) {
			visited[i]--;
			answer.push_back('a' + i);
			dfs(index + 1, size);
			answer.pop_back();
			visited[i]++;
		}
	}
}

void solve() {
	for (int i = 0; i < 26; i++) {
		visited[i] = 0;
	}
	answer = "";
	int size = str.size();
	for (int i = 0; i < size; i++) {
		visited[str[i] - 'a']++;
	}
	dfs(0,size);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);


	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> str;
		solve();
	}
}