Problem
Key Idea
โeach letter is included in no more than one pair.โ
a๊ฐ forbidden pair {a,b}์ ๋ฑ์ฅํ๋ค๋ฉด, {a,c}์ ๊ฐ์ด ๋ ๋ฑ์ฅํ์ง๋ ์๊ธฐ ๋๋ฌธ์,
substring ๋ง๋ค ๊ฐ๊ฐ ๋
๋ฆฝ์ ์ผ๋ก ํ ์ ์๋ค.
์๋ฅผ ๋ค์ด, forbidden pair๊ฐ {a,b}, {x,y} ์ผ๋
์ฃผ์ด์ง ๋ฌธ์์ด์ด aabxyyxyxyxabcdabxxxy ๋ผ๋ฉด
aab / xyyxyxyx / ab / cd / ab / xxxy ๋ก ๋๋ ์ ๊ฐ substring ๋ง๋ค ์ต์ ๊ฐ์๋ฅผ ์ฐพ์ผ๋ฉด ๋๋ค๋ ์๊ธฐ.
- ์ง์ฐ๋ letter๋ฅผ ์ต์๋ก ํ๊ธฐ ๋๋ฌธ์, ๊ฐ substring์์ ์ต์ ํ๋๋ ๋จ๊ฒ ๋๋ค. ๋ฐ๋ผ์ ๊ฐ substring ๋ง๋ค ์ฐพ์ ์ต์ ์ญ์ ํ์๋ฅผ ๋จ์ํฉ ํด์ฃผ๋ฉด ๋ต์ด ๋๋ค.
- ๊ฐ substring์์, ๋ letter ์ค ์ ์ ๋น๋๋ก ๋ฑ์ฅํ๋ letter๋ฅผ ์ ๋ถ ์ญ์ ํด์ผ ๋๋ค.
๋ฐ๋ผ์,
- forbidden pair๋ก ์ด๋ฃจ์ด์ง substring(continuous subsequence) ๋ค์ ์ฐพ๊ณ ,
- ๊ทธ ๊ฐ๊ฐ์์ ์ญ์ ํด์ผ ํ๋ ์ต์ letter์(greedy)๋ฅผ ๋ํด์ค๋ค.
- Time: \(O( k \cdot \lvert s \rvert )\)
Implementation
/**
* author: jooncco
* written: 2021. 5. 8. Sat. 23:05:16 [UTC+9]
**/
#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(0),cin.tie(0)
string str, forbidden[20];
int k;
int main() {
FAST_IO;
cin >> str >> k;
int len= str.length();
vector<vector<string>> arr;
for (int i=0; i < k; ++i) {
vector<string> vec; // k๋ฒ์งธ forbidden pair๋ก ์ด๋ฃจ์ด์ง substring๋ค์ ์ ์ฅํ๋ array
cin >> forbidden[i];
// forbidden[i]์ letter๋ค๋ก ์ด๋ฃจ์ด์ง substring์ ์ฐพ์ vec์ ์ ์ฅ
bool subStr= 0;
string S= "";
for (int idx=0; idx < len; ++idx) {
if (str[idx] == forbidden[i][0] || str[idx] == forbidden[i][1]) {
if (subStr) {
S.push_back(str[idx]);
}
else {
subStr= 1;
S= string(1,str[idx]);
}
}
else {
if (subStr) {
vec.push_back(S);
S= "";
}
subStr= 0;
}
}
if (subStr) vec.push_back(S); // ๋ง์ง๋ง substring๋ ๋์น์ง ๋ง์
arr.push_back(vec);
}
int ans= 0;
for (int i=0; i < k; ++i) {
// i๋ฒ์งธ substring์ ๋ํด ์ต์๋ก ์ญ์ ํด์ผํ๋ letter์๋ฅผ ans์ ๋ํด์ค๋ค.
for (int j=0; j < arr[i].size(); ++j) {
int cnt[2]= {0};
string s= arr[i][j];
for (int idx= 0; idx < s.length(); ++idx) {
if (s[idx] == forbidden[i][0]) ++cnt[0];
if (s[idx] == forbidden[i][1]) ++cnt[1];
}
if (cnt[0] < cnt[1]) ans += cnt[0];
else ans += cnt[1];
}
}
cout << ans;
}
Leave a comment