어흥
[백준 6443] 애너그램 (C++) 본문
728x90
반응형
문제 링크: www.acmicpc.net/problem/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;
}
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