SKK 문자열

백준 24525번: SKK 문자열

아이디어

문자열에 포함된 K의 개수가 S의 개수의 2배여야 한다. S는 2, K는 -1, 그 외 글자는 0으로 해서 배열을 만들고, prefix sum을 구한다. 각 prefix sum의 값을 가지는 최소 인덱스를 기록하면 가장 긴 부분 문자열의 길이를 구할 수 있다.
‘ ‘ A B S S K K K
0 0 0 2 4 3 2 1

prefix sum 값이 같은 경우가 부분 문자열에 포함된 K의 개수가 S의 개수의 2배인 경우다.
이 때 사이에 S 혹은 K가 하나도 없으면 성립하지 않으므로 각 인덱스에 S 혹은 K가 몇 개 존재하는지 기록해 놓아야 한다.

코드

#include <bits/stdc++.h>

using namespace std;

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

    // S = 2, K = -1
    string s;
    cin >> s;
    vector<int> v(s.size()+1), cnt(s.size()+1);
    map<int, int> minidx;
    for (int i = 0; i < s.size(); i++) {
        int n = 0;
        if (s[i] == 'S') n = 2;
        if (s[i] == 'K') n = -1;
        v[i+1] = v[i] + n;
        cnt[i+1] = cnt[i] + (n == 0 ? 0 : 1);
    }

    int ans = -1;

    for (int i = 0; i < s.size()+1; i++) {
        if (minidx.find(v[i]) == minidx.end()) {
            minidx[v[i]] = i;
        }
        else {
            int midx = minidx[v[i]];
            if (cnt[midx] == cnt[i]) continue;
            ans = max(ans, i-midx);
        }
    }

    cout << ans;

    return 0;
}

여담

2달 전에 못풀었던거 기억나서 다시 풀어봤다. prefix sum 문제 많이 풀어봐야겠다. 인덱스를 기록하는 경우가 많은듯.