[ 백준 1342 ] 행운의 문자열 (C++)

백준의 행운의문자열(1342) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 문제에서 말하는 행운의 문자열이 무엇인지 부터 다시한번 확인해보자. 문자열이 있으면, 서로 인접해 있는 모든 문자가

   다르다면 행운의 문자열이라고 했다.

   즉, abc, aba, bab 모두 행운의 문자열이 되는 것이다.

   입력으로 주어지는 문자열에서 행운의 문자열의 갯수를 찾는것이 문제이다.

   구현하는 과정이 조금 복잡하니, 큰 틀과 큰 틀에 대한 이유를 알아보자.

   물론, 지금부터 하는 말이 정답이 절대 아니고 본인이 구현하면서 생각해낸 코드이니 참고만 할 것 ! 정답이 아니다 !

  1. 입력으로 주어진 문자열에서 각각의 알파벳 갯수를 저장해두기

   → 너무 뜬금없는 소리일 수도 있다. 이 부분에 대한 설명은 거의 마지막 부분에 다시 설명해보겠다.

      무튼 본인은, 처음 입력한 문자열에서 알파벳의 갯수를 저장해두었다.

      "abc" 라면 a = 1, b = 1 , c = 1, "aab" 라면 a = 2 , b = 1 이런식으로 26칸짜리 배열을 만들어서 저장해주었다.

  2. 입력으로 주어진 문자열에서 나올 수 있는 모든 문자열 찾기

   → 본인은 입력으로 주어진 문자열에서 나올 수 있는 모든 문자열을 찾아서, 행운의 문자열인지 판단하였다.

      즉, 주어진 문자열에서 나올 수 있는 순열을 모두 구해보았다.

      ex) 입력이 "abc"라고 하면, "abc", "acb", "bac", "bca", "cab", "cba" 모두 구해보고, 행운의 문자열인지 판단해주었다.

      순열을 구하는 방법을 잘 모른다면 아래의 링크를 타고 글을 하나 읽어보고 오자 !

      [ 순열 구현하기(Click) ]

  3. 2번에서 찾은 모든 문자열 중에서, 행운의 문자열 갯수를 찾아냈다면, 그 갯수를 Factorial로

    나누기 !

   → 갑자기 무슨소리인지 당황스럽다. 구체적인 예를 통해서 위에 과정이 왜 필요한지 무엇을 하기 위한 작업인지 알아보자.

      예를 들어서 "abc"라는 문자열이 있다고 가정해보자.

      이 때, 생성될 수 있는 모든문자열과, 행운의 문자열은 동일하게 "abc" , "acb", "bac", "bca", "cab", "cba"로 총 6개가

      된다.

      다른 예를 한번 생각해보자. "aab" 라는 문자열이 있다고 가정해보자.

      이 때 생성될 수 있는 모든 문자열은 "aab", "aba", "baa" 3개가 되고, 여기서 행운의 문자열은 "aba" 1개이다. 하지만,

      직접 구현해보면 알겠지만, 행운의 문자열이 2개가 나오게 될 것이다. "aba", "aba" 이렇게 2개가 나오게 될 것이다. 

      사실 위의 2개의 문자열은 컴퓨터 입장에서는 처리하는데 동일한 문자열이 아니다. a가 2개이기 때문에 1번a 2번a를

      다르게 계산한다고 치면, 행운의 문자열 갯수가 저렇게 2개가 나오게 된다.

      사실 생성될 수 있는 모든 문자열도 "aab", "aba", "baa" 3개라고 말했지만, 훨씬 더 많은 갯수가 나올 것이다.

      이 부분을 처리해줘야 한다. 우리 입장에서는 "aba" 나 "aba"나 같은 문자열이기 떄문에 2개로 Count하는 것이 아닌,

      1개로 Count 해줘야 한다. 이를 위해서 우리는 1번에서 문자열에 들어있는 알파벳의 갯수를 저장해 주었다.

      "aba"에서는 a는 2개, b는 1개라고 저장되어 있을 것이다. 그리고 행운의 문자열의 갯수는 2개로 저장되어 있을 것이다.

      이 2개라는 결과에서, a의 Factorial 값과 1의 Factorial 값으로 나눠보자.

      2 / (2 ! x 1!) = 1 로 1이라는 결과가 나오게 된다. 즉, 우리는 이렇게 동일한 문자에 대해서 여러번 처리 되는 것을

      방지하기 위해서, 각 알파벳의 갯수의 Factorial 값으로 나눠 버리면, 중복을 처리할 수 있다.

     

      예제 입력 1에서도 마찬가지이다. 예제 입력 1을 보면 "aabbbaa" 인데, 행운의 문자열 갯수를 모두 구해보면

      144개라는 결과가 나온다. 이 값에서 a의 갯수인 4, b의 갯수인 3의 팩토리얼 값으로 나눠버리게되면

      144 / (4 ! x 3 !) 을 하게 되면 결과가 1이 나온다는 것을 알 수 있고 실제 정답도 1이라는 것을 확인할 수 있다.

위의 내용을 모두 이해했다면, 코드 자체는 그리 어렵지 않으니 소스코드를 참고하면 쉽게 풀 수 있을 것이라 생각한다.

[ 소스코드 ]

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
 
#define endl "\n"
#define MAX 10
using namespace std;
 
string Inp;
int Len, Answer;
int Alphabet[26];
char Arr[MAX];
bool Select[MAX];
vector<char> V;
 
void Input()
{
    cin >> Inp;
    Len = Inp.length();
 
    for (int i = 0; i < Len; i++)
    {
        Alphabet[Inp[i] - 'a']++;
        Arr[i] = Inp[i];
    }
}
 
bool IsLucky()
{
    for (int i = 0; i < V.size() - 1; i++)
    {
        if (V[i] == V[i + 1]) return false;
    }
    return true;
}
 
void DFS(int Cnt)
{
    if (Cnt == Len)
    {
        if (IsLucky() == true) Answer++;
        return;
    }
 
    for (int i = 0; i < Len; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        V.push_back(Arr[i]);
        DFS(Cnt + 1);
        Select[i] = false;
        V.pop_back();
    }
}
 
int Factorial(int n)
{
    int R = 1;
    for (int i = n; i >= 1; i--)
    {
        R = R * i;
    }
    return R;
}
 
void Solution()
{
    DFS(0);
    for (int i = 0; i < 26; i++)
    {
        if (Alphabet[i] > 1)
        {
            Answer = Answer / Factorial(Alphabet[i]);
        }
    }
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}