[백준 6443] 애너그램 (C++)

문제 링크: www.acmicpc.net/problem/6443

6443번: 애너그램

1. 주의할 점

- 문자열의 길이가 최대 몇인지 모른다 -> 배열을 이용해서 풀기 애매하다

- 문자열의 길이가 최대 몇인지 모르므로 Set을 사용하기 애매하다 -> TLE나 메모리초과가 날 수도 있다

 

2. 구현

- 그리디를 통해 접근한다

- 문자열을 입력받을 때, Sort 작업 수행과 Len을 설정한다

- DFS() 함수를 통해 idx가 문자열 길이-1일때 문자열을 출력한다

- For문을 통해 현재 바꾸려고 하는 위치의 문자와 다른 문자가 같은 숫자라면 Continue

- 다른 문자를 보유했다면 스왑한다

 

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string str;
int len;

void dfs(string s, int idx) {
	if (idx == len - 1) {
		cout << s << '\n';
		return;
	}
	for (int i = idx; i < len; i++) {
		if (i != idx && s[i] == s[idx])
			continue;
		if(s[i] != s[idx]){
			char c = s[i];
			s[i] = s[idx];
			s[idx] = c;
		}
		dfs(s, idx + 1);
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int test;
	cin >> test;
	while (test) {
		cin >> str;
		len = str.size();
		sort(str.begin(), str.end());
		dfs(str, 0);
		test--;
	}
	return 0;
}