[ 백준 9177 ] 단어 섞기 (C++)

백준의 단어섞기(9177) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 사실 본인은 처음에 이 문제에 접근할 때, 주어진 2개의 문자열을 합쳐서 구현할 수 있는 모든 순열을 다 구현해보고, 정답과

   동일한 순열이 나온다면 yes를 출력하는 식으로 구현하였는데 시간초과에 걸렸다.

   뭔가 모든 경우를 다 해보고, 답인 경우를 찾는 방식이라면 시간초과에 걸리는 것 같아서 방법을 바꿔보았다.

   본인은 먼저 입력과 동시에 답을 출력하는 경우를 하나 만들었다.

   입력받는 첫 번째 두 번째 단어에 있는 알파벳들의 갯수를 Count해주었다.

   "ABC" 와 "BCD" 라면 A = 1개 , B = 2개, C = 2개 , D = 1 개 이런식으로 말이다. 그리고, 만들어야 하는 세번째 단어를 입력받으면서

   알파벳들의 갯수를 Count해 주었다.

   즉, 첫 번째 두번째 단어를 합친 알파벳의 갯수와, 세번째 단어의 알파벳의 갯수를 비교봤을 때, 0이 아니면서 값이 다른 알파벳

   이 존재한다면 절대로 만들 수 없는 경우라는 것이다.

   "ABC"와 "BCD"가 첫번째 두번째 단어로 주어지고, "DEF"가 주어졌다고 생각해보자. E와 F가 0개 이기 때문에, 어떻게 합쳐도

   절대로 답이 나올 수가 없다. 따라서 이런 경우를 한번 처리해주고 시작하였다.

2) 본격적인 풀이에 들어가보자. 본인은 DFS로 재귀를 호출하면서 단어를 맞춰갔는데, 이 때, 문자열의 Index를 많이 사용하였다.

   예제입력1 로 알아보자. "cat" 과 "tree" 그리고,"catrtee" 가 있다고 생각해보자.

   "cat"에서 'c'는 0번째, 'a'는 1번째, 't'는 2번째 Index이다.

   이런식으로 문자열에 Indexing한 방식을 이용해주었따.

   DFS함수에 들어가는 매개변수로는 (첫번째 문자열의 현재 Index번호, 두번째 문자열의 현재Index번호, 세번째 문자열의 현재

   Index번호) 를 사용해주었다.

   사실 본문 코드에 보면, 매개변수가 한개가 더있는데 사실 없어도 되는 변수인것 같다.

   이 후, 각 문자열의 현재 Index번호를 통해 가져온 문자와, 세번째 문자열의 Index번호를 통해 가져온 문자를 비교해서

   같다면, 해당 문자열의 Index번호만 추가하는 식으로 구현해주었다.

   "cat" , "tree", "catrtee"가 있을 때,

   첫 번째 문자열의 0번째 문자인 'c'와 세 번째 문자열의 0번째 문자인 'c'를 비교.

   두 번째 문자열의 0번째 문자인 't'와 세 번째 문자열의 0번째 문자인 'c'를 비교 했을 때, 전자가 일치하기 때문에

   재귀를 DFS(첫 번재 문자열의 현재 Index번호 + 1, 두 번째 문자열의 현재 Index번호, 세 번째 문자열의 Index번호 + 1)

   이런식으로 재귀를 구현해 주었다.

   재귀의 종료조건은, 세 번째 문자열의 Index번호가 세 번째 문자열의 길이와 같아질 경우 종료해 주었다.

[ 소스코드 ]

#include<iostream>
#include<string>
#include<cstring>
#include<queue>
 
#define endl "\n"
#define MAX 200
using namespace std;
 
string A, B, Result;
 
int Before_Alphabet[26], A_Len, B_Len;
int Result_Alphabet[26], R_Len;
bool Before_Answer, After_Answer;
bool Visit[MAX][MAX];
 
void Initialize()
{
    A.clear();
    B.clear();
    Result.clear();
    A_Len = B_Len = R_Len = 0;
    Before_Answer = true;
    After_Answer = false;
 
    memset(Before_Alphabet, 0, sizeof(Before_Alphabet));
    memset(Result_Alphabet, 0, sizeof(Result_Alphabet));
    memset(Visit, false, sizeof(Visit));
}
 
void Input()
{
    cin >> A >> B >> Result;
    A_Len = A.length();
    B_Len = B.length();
    R_Len = Result.length();
 
    for (int i = 0; i < A_Len; i++)
    {
        int Temp;
        if ('A' <= A[i] && A[i] <= 'Z') Temp = A[i] - 'A';
        else Temp = A[i] - 'a';
 
        Before_Alphabet[Temp]++;
    }
 
    for (int i = 0; i < B_Len; i++)
    {
        int Temp;
        if ('A' <= B[i] && B[i] <= 'Z') Temp = B[i] - 'A';
        else Temp = B[i] - 'a';
 
        Before_Alphabet[Temp]++;
    }
 
    for (int i = 0; i < R_Len; i++)
    {
        int Temp;
        if ('A' <= Result[i] && Result[i] <= 'Z') Temp = Result[i] - 'A';
        else Temp = Result[i] - 'a';
 
        if (Before_Alphabet[Temp] == 0)
        {
            Before_Answer = false;
            return;
        }
 
        Result_Alphabet[Temp]++;
    }
 
    for (int i = 0; i < 26; i++)
    {
        if (Result_Alphabet[i] == 0) continue;
        if (Result_Alphabet[i] != Before_Alphabet[i])
        {
            Before_Answer = false;
            return;
        }
    }    
}
 
void DFS(int A_Idx, int B_Idx, int R_Idx, string S)
{
    if (After_Answer == true) return;
    if (R_Idx == R_Len)
    {
        After_Answer = true;
        return;
    }
 
    char ch_A = A[A_Idx];
    char ch_B = B[B_Idx];
    char ch_R = Result[R_Idx];
 
    if (A_Idx < A_Len && ch_A == ch_R) DFS(A_Idx + 1, B_Idx, R_Idx + 1, S + ch_A);
    if (B_Idx < B_Len && ch_B == ch_R) DFS(A_Idx, B_Idx + 1, R_Idx + 1, S + ch_B);
}
 
void Solution()
{
    DFS(0, 0, 0, "");
}
 
void Solve()
{
    int Tc;
    cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        if (Before_Answer == false)
        {
            cout << "Data set " << T << ": no" << endl;
            continue;
        }
        Solution();
 
        if (After_Answer == true)
        {
            cout << "Data set " << T << ": yes" << endl;
        }
        else
        {
            cout << "Data set " << T << ": no" << endl;
        }
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}