어흥

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

알고리즘/백준

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

라이언납시오 2020. 10. 4. 14:17
728x90
반응형

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

 

6443번: 애너그램

N개의 영단어에 대한 모든 가능한 애너그램을 출력한다. 각각의 영단어에 대한 애너그램을 출력할 때, 알파벳 순서로 중복되지 않게 출력한다.

www.acmicpc.net

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;
}
728x90
반응형

'알고리즘 > 백준' 카테고리의 다른 글

[백준 1965] 상자넣기 (C++)  (0) 2020.10.07
[백준 1800] 인터넷 설치 (C++)  (0) 2020.10.04
[백준 1175] 배달 (C++)  (0) 2020.10.02
[백준 11451] 팩맨 (C++)  (0) 2020.09.28
[백준 1495] 기타리스트 (C++)  (0) 2020.09.28
Comments