[백준,c++] 6443번 - 애너그램

문제

6443번: 애너그램

 

코드

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    int N; cin>>N;
    while(N--){
        string inp; cin>>inp;
        
        sort(inp.begin(), inp.end());
        do{
            cout<<inp<<'\n';
        }while(next_permutation(inp.begin(), inp.end()));
    }
}

 

풀이

해당 알파벳으로 만들 수 있는 모든 경우를 구하는 순열 문제였는데 next_permutation을 사용해서 구현했습니다. 처음에 아래와 같이 직접 순열을 구현했는데 계속 시간 초과가 발생해서 방안을 찾지 못하고 next_permutation을 사용했습니다.

#include <iostream>
#include <vector>
#include <memory.h>
#include <algorithm>
#include <unordered_map>

using namespace std;
vector<string> ans;
bool visited[100001];
unordered_map<string,int> check;

void dfs(string make, string inp){
    if(inp.length() == make.length()){   // 바로바로 출력해야 한다. 저장한 후에 출력하면 메모리 초과 발생
        if(!check[make]){
            check[make]++;
            cout<<make<<'\n';
            return;
        }
    }
    for(int i=0; i<inp.length(); i++){
        if(visited[i]) continue;
        visited[i] = 1;
        dfs(make+inp[i], inp);
        visited[i] = 0;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N; cin>>N;
    
    for(int i=0; i<N; i++){
        string inp; cin>>inp;
        sort(inp.begin(), inp.end());   // 정렬을 한 후에 백트랙킹을 돌리자.
        dfs("", inp);
        memset(visited, 0 ,sizeof(visited));
    }
}