BOJ 33602 Mascot Naming

문제 링크입니다.

문제 요약

주어진 $N$개의 패턴 문자열 $S$를 모두 부분수열¹로 가지면서, 주어진 특정 금지 문자열 $P$는 부분수열로 갖지 않는 문자열을 찾으세요. 문자열의 길이가 최소가 될 필요는 없습니다.

풀이

$S$들 중에서 $P$를 부분수열로 갖는 것이 있으면 답은 자명히 NO가 됩니다. 이러한 경우를 배제하겠습니다.

$S$들을 $P$를 기준으로 그리디하게 분할합니다. 뭔 말이냐 하면, $S$ 안에서 $P$의 접두사를 찾고, 그 접두사를 칸막이로 생각하는 겁니다. 그러면, 같은 칸에 들어있는 모든 $S$의 조각들을 아무렇게나 나열해도 찾아진 금지 문자열의 접두사 길이가 증가하지 않음을 알 수 있습니다.

따라서 첫 번째 칸에 들어간 모든 문자열 조각을 나열하고, 금지 문자열의 첫 번째 문자를 추가하고, 두 번째 칸의 모든 문자열 조각을 나열하고… 하는 것을 반복하면 $P$를 포함하지 않으면서 모든 $S$를 포함하는 문자열을 얻을 수 있습니다.

코드

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

vector<string> s;
vector<char> c[202020];

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	int n; cin >> n; s.resize(n);
	for(int i = 0; i < n; i++) cin >> s[i];
	string t; cin >> t;
	string ans = "";
	for(int i = 0; i < n; i++){
		int r = 0;
		for(int j = 0; j < s[i].size(); j++){
			if(s[i][j] == t[r]){
				r++;
				if(r == t.size()) return !(cout << "NO");
			}
			else c[r].push_back(s[i][j]);
		}
	}
	cout << "YES\n";
	for(int i = 0; i < t.size(); i++){
		for(auto x : c[i]) cout << x;
		if(i != t.size()-1) cout << t[i];
	}
}

---

1. 어떤 문자열의 부분수열(subsequence)은 그 문자열에서 0개 이상의 문자를 제거한 뒤 남은 문자를 순서를 바꾸지 않고 이어붙인 문자열입니다. ↩︎