[BOJ 24978] Subset Equality

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

24978번: Subset Equality

 

- 문제 요약

 

소들은 암호화된 메시지를 교환하는 새로운 방법을 시도해보고 있습니다.
그들은 메시지 해독을 어렵게 하기 위해 관련 없는 문자들을 중간중간 섞습니다.

소들은 두 문자열 S와 T를 전송합니다.
S와 T는 영어 소문자 'a'부터 'r'로만 구성되며, 길이는 최대 10^5입니다.
이 문자열을 이해하기 위한 쿼리 Q(1<=Q<=10^5)가 주어지며, 각 쿼리는 'a'에서 'r'까지의 하위 집합을 제공합니다.
각 쿼리의 문자로만 S와 T의 문자가 제한되는 경우, s와 t가 동일한지에 대한 여부를 한 줄로 출력하세요.

s와 t가 동일하다면 'Y', 아니면 'N'을 출력하세요.

 

 

- 알고리즘 정리

 

Q개의 줄에 주어지는 쿼리를 q라고 했을 때, q에 있는 알파벳들만 사용한 두 문자열 S와 T가 같다면, q의 부분 집합 qq에 있는 알파벳만 사용한 두 문자열 역시 같습니다.

집합 q={s1, s2, ... , sk}만 사용했을 때 S와 T가 같다면, 임의의 1<=i<=j<=k에 대해 {si, sj}를 사용한 문자열 역시 같습니다.

그렇기에 모든 집합에 대한 S와 T가 동일한지 전처리 해주고 풀이를 하게 되면 시간 내에 문제를 해결 할 수 있습니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 100001
string s,t;
int q,n,m,arr[MAX],brr[MAX];
bool crr[18][18];

bool f(int x){
	vector<int>a,b;
	for(int i=0;i<n;i++){
		if(x>>arr[i]&1){
			a.push_back(arr[i]);
		}
	}
	for(int i=0;i<m;i++){
		if(x>>brr[i]&1){
			b.push_back(brr[i]);
		}
	}
	return a==b;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>s>>t>>q;
	n=s.size(),m=t.size();
	for(int i=0;i<n;i++){
		arr[i]=s[i]-'a';
	}
	for(int i=0;i<m;i++){
		brr[i]=t[i]-'a';
	}
	for(int i=0;i<18;i++){
		for(int j=0;j<18;j++){
			crr[i][j]=f((1<<i)|(1<<j));
		}
	}
	for(int qq=0;qq<q;qq++){
		string s;
		cin>>s;
		bool flag=true;
		for(auto i:s){
			for(auto j:s){
				flag&=crr[i-'a'][j-'a'];
			}
		}
		cout<<(flag?'Y':'N');
	}
}

코드 제출 결과