백준 1342. 행운의 문자열

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

1342번: 행운의 문자열

 

1. 재귀로 순열을 만들듯이 모든 가능한 문자열 조합을 만든다

2. 만들어진 문자열이 행운의 문자열인지 판별한다

3. 행운의 문자열이라면 벡터에 푸쉬한다

4. 모든 문자열 조합에 대하여 계산이 끝난후 sort, unique, erase 함수를 이용해 중복을 제거한다

5. 벡터의 크기가 답이다

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

string str;
string temp;
vector<string> ans;
bool mark[10];

// string temp의 string이 인접해 있는 모든 문자가 같지 않으면 lucky
bool IsItLucky()
{
    if(temp[0] == temp[1]) return false;
    if(temp[temp.size()-1] == temp[temp.size()-2]) return false;

    for(int i = 1; i < temp.size()-1; i++)
    {
        if(temp[i] == temp[i-1] || temp[i] == temp[i+1])
            return false;
    }
    return true;
}

void Arrange(int depth)
{
    if(depth == str.size())
    {
        // 만들어진 문자열이 행운의 문자열인지 판단
        if(IsItLucky())
            ans.push_back(temp);

        return;
    }

    for(int i = 0; i < str.size(); i++)
    {
        if(mark[i]) continue;
        mark[i] = true;
        temp.push_back(str[i]);
        Arrange(depth+1);
        temp.pop_back();
        mark[i] = false;
    }
}

int main()
{
    cin >> str;
    Arrange(0);

    // 정렬후 중복 제거
    sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(),ans.end()), ans.end());

    cout << ans.size();
}

 

---

다른 분들 풀이를 보고 더 빠른 방법을 찾았다.

처음에 주어진 문자열에서 각 알파뱃의 갯수를 기억해 놨다가

 

사용할수 있는 알파벳들을 사용해서 공백의 문자열에서부터 문자열의 끝과 다른 문자를 계속 추가해 나간다.

주어진 문자열의 크기만큼 문자열이 만들어졌으면 그 문자열은 행운의 문자열이므로 카운트를 늘린다.

 

#include <iostream>
#include <string>
using namespace std;

string str;
int alp[26];
int ans = 0;

// 사용할수 있는 알파벳들로 행운의 문자열을 만든다
void MakeString(int depth, string s)
{
    if(depth == str.size())
    {
        ans++;
        return;
    }

    for(int i = 0; i < 26; i++)
    {
        // 해당 알파벳 개수 소진했으면 continue
        if(alp[i] == 0) continue;
        // 만들어진 문자열 s의 끝문자와 다른 문자만 이어붙인다
        // 처음에 s가 비어있을때는 아무 문자나 넣어도 된다
        if(s != "" && (char)('a'+i) == s[s.size()-1]) continue;

        alp[i]--;
        MakeString(depth+1, s + (char)('a'+i));
        alp[i]++;
    }

}

int main()
{
    cin >> str;

    // str의 알파벳 개수 저장
    for(int i = 0; i < str.size(); i++)
        alp[str[i]-'a']++;

    MakeString(0, "");

    cout << ans;
}