[백준 25328번] 문자열 집합 조합하기 (C++)

문제링크 : https://www.acmicpc.net/problem/25328

25328번: 문자열 집합 조합하기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

string x, y, z;
int K;
map<string, int> m;

void backtracking(int idx, string str, string tmp)
{
    if(tmp.size() == K)
    {
        m[tmp]++; //해당 문자열 갯수 증가
        return;
    }

    for(int i=idx; i<str.size(); i++)
    {
        backtracking(i+1, str, tmp+str[i]); //하나씩 검토
    }
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> x >> y >> z;
    cin >> K;
    backtracking(0, x, ""); //각각 문자열로 백트래킹
    backtracking(0, y, "");
    backtracking(0, z, "");

    bool flag = false;
    for(auto i : m)
    {
        if(i.second >= 2) //두 번이상 나타나는 것만 출력
        {
            cout << i.first << "\n";
            flag = true;
        }
    }

    if(!flag) cout << -1; //없음
    return 0;
}

각각의 문자열들을 백트래킹을 통해서 하나씩 검토해준다.

이때 문자열을 하나씩 더해주는 tmp의 사이즈가 K와 같아지면 해당 tmp 문자열의 갯수를 더해준다 (m[tmp]++)

이를 x, y, z 각각의 문자열에 대해 전부 확인해준다.

 

이후에 map에 저장된 각 문자열들의 int 값을 확인하고 이 값이 2이상, 즉 두 번이상 나타난 것만 출력하도록 한다.

두 번이상 나타나는 것이 없을 경우에는 표시용으로 사용한 flag를 확인하여 -1을 출력하도록 한다.