[BOJ] 백준 6443 애너그램

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

 Input 

2

abc

acba

　 

 Output 

abc

acb

bac

bca

cab

cba

aabc

aacb

abac

abca

acab

acba

baac

baca

bcaa

caab

caba

cbaa

 

중복을 제거해서 순열을 구하는 문제입니다.

---

DFS 이용한 코드

#include <iostream>
#include<string>
using namespace std;
 
int N, len, alphabet[26];
string str;
char output[1001];
 
void DFS(int idx, int depth) {
    if (depth == len) {
        cout << output << '\n';
        return;
    }
 
    for (int i = 0; i < 26; i++) {
        if (alphabet[i] > 0) {
            alphabet[i]--;
            output[depth] = 'a' + i;
            DFS(i, depth + 1);
            alphabet[i]++;
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    while(N--){
        for (int i = 0; i < 26; i++)
            alphabet[i] = 0;
        
        cin >> str;
        len = str.length();
        for (int i = 0; i < len; i++) {
            alphabet[str[i] - 'a']++;
        }
 
        DFS(0, 0);
    }
}

 

STL::next_permutation() 이용

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
 
bool cmp(char a, char b){
    return a < b;
}
 
int N;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    while(N--){
        char str[105] = {0, };
        cin >> str;
        int len = strlen(str);
        sort(str, str + len);
        
        do{
            printf("%s\n", str);
        } while (next_permutation(str, str + len, cmp));
    }
}