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๋ฅผ ์ „๋ถ€ ์‚ญ์ œํ•ด์•ผ ๋œ๋‹ค.


๋”ฐ๋ผ์„œ,

  1. forbidden pair๋กœ ์ด๋ฃจ์–ด์ง„ substring(continuous subsequence) ๋“ค์„ ์ฐพ๊ณ ,
  2. ๊ทธ ๊ฐ๊ฐ์—์„œ ์‚ญ์ œํ•ด์•ผ ํ•˜๋Š” ์ตœ์†Œ 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;
}


Tags:

Updated:

Leave a comment