[BOJ 25328 // C++] 문자열 집합 조합하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 25328번 문제인 문자열 집합 조합하기이다.
문제는 아래 링크를 확인하자.

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

 

주어지는 각 문자열의 길이는 최대 17임을 확인하자. 즉, 각 문자열은 부분문자열을 많아야 \(2^{17} - 1\)개 존재하며(빈 문자열 제외), 그 중 특정 길이의 문자열만 세면 그 개수는 더욱 적어지고 각 문자열의 길이는 17 이하임을 확인하자. 또한, 주어지는 각 문자열에는 중복된 문자가 존재하지 않으므로 한 문자열에서 조합한 모든 문자열은 서로 다름을 확인하자.

 

따라서 각 문자열에 대하여 조합 가능한 모든 문자열에 한 번씩 접근해보면서 주어진 세 문자열에서 총 몇 회 등장했는지 기록하는 것으로 문제를 충분히 해결할 수 있다.

 

아래는 제출한 소스코드이다.

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

int K;
string X, Y, Z;
string A;
map<string, int> mp;

void func(int idx, string &s) {
	if (A.length() == K) {
		mp[A]++;
		return;
	}
	if (idx == s.length()) return;
	A += s[idx];
	func(idx + 1, s);
	A.pop_back();
	func(idx + 1, s);
}

bool prnt;

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

	cin >> X >> Y >> Z >> K;
	func(0, X); func(0, Y); func(0, Z);
	for (auto &p : mp) {
		if (p.second > 1) cout << p.first << '\n', prnt = 1;
	}
	if (!prnt) cout << -1;
}