백준 24524번 아름다운 문자열

백준 24524번: 아름다운 문자열

아이디어

만들어야 하는 문자가 현재 몇 개 나왔는지 기록한다. 이 때 자기보다 한 칸 앞서서 나와야 하는 문자의 개수가 자기 자신보다 많은 경우에만 증가시킨다. 예를 들어 abcd를 찾는다 하면 현재 a를 2개, b를 1개, c를 1개 찾은 상태에서 다음 알파벳이 b인 경우 b의 개수를 증가시킬 수 있지만 다음 알파벳이 c인 경우 c의 개수를 증가시킬 수 없다. b가 모자라기 때문. 마지막 알파벳인 d까지 다 찾은 경우, 각 알파벳의 개수를 1개씩 빼주고 최종 개수를 1 증가시킨다.

코드

#include <bits/stdc++.h>

using namespace std;

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

    string s, t;
    cin >> s >> t;

    vector<int> v(t.size());
    int ans = 0;

    for (int i = 0; i < s.size(); i++) {
        for (int j = 0; j < t.size(); j++) {
            if (s[i] == t[j]) {
                if (!j) v[j]++;
                else if (v[j-1] > v[j]) v[j]++;
            }
            if (v[t.size()-1]) {
                for (int k = 0; k < t.size(); k++) {
                    v[k]--;
                }
                ans++;
            }
        }
    }

    cout << ans;

    return 0;
}

여담

대회때 이거 푸는데 갑자기 누구 탈영했다고 집합시켜서 오래걸림;;