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

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

 

 

이 문제는 N개의 문자열이 주어지며 각각의 문자열에 대해서

알파벳 순서대로 출력해야하는 문제이다.

 

단어의 최대 길이는 20이며 에너그램(바꿀 수 있는 단어의 개수)는 최대 10만개이다.

즉 백트래킹을 사용하여 알파벳순서대로 나온 가지 수를 출력하면 되는 문제이다.

 

하지만 C++에서는 next_permutation 내장된 함수가 있기 때문에 쉽게 풀 수 있다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {0, -1, 0, 1, 1, -1, -1, 1};
int dy[] = {-1, 0, 1, 0, -1, 1, -1, 1};
int N;
vector<char> v;

void solve() {
    sort(v.begin(), v.end());

    do {
        for(auto it = v.begin(); it != v.end(); it++) {
            cout << *it;
        }
        cout << endl;
    } while(next_permutation(v.begin(), v.end()));
}

void input() {
    cin >> N;

    for(int i = 0; i < N; i++) {
        string s;
        cin >> s;

        for(int j = 0; j < s.size(); j++) {
            v.push_back(s[j]);
        }

        solve();
        v.clear();
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
}

 

 

input함수부터 살펴보면

void input() {
    cin >> N;

    for(int i = 0; i < N; i++) {
        string s;
        cin >> s;

        for(int j = 0; j < s.size(); j++) {
            v.push_back(s[j]);
        }

        solve();
        v.clear();
    }
}

 

입력된 문자열을 벡터에 저장하여 먼저 정렬한다. 사전순이기 때문에 입력된 문자열에서도 순서대로 출력을 해야하기 때문이다.

 

이후 solve함수를 살펴보면

void solve() {
    sort(v.begin(), v.end());

    do {
        for(auto it = v.begin(); it != v.end(); it++) {
            cout << *it;
        }
        cout << endl;
    } while(next_permutation(v.begin(), v.end()));
}

 

벡터에 저장한 문자에 대해서 사전순으로 순열을 구성해여 문자를 출력한다.