BOJ 20437 - 문자열 게임2

https://www.acmicpc.net/problem/20437

 

생각한대로 풀려서 기분이 너무 좋았다. 

findLongestSubArray문제를 풀어봤던 것이 도움이  됐다.

 

알파벳이 몇개 나왔나 카운트 하는 배열이 있고,

어떤 글자가 어떤 인덱스에 나왔다 저장하는 벡터 배열을 만든다.

vector<int> loc[30]; // 어떤 글자가 나온 인덱스들을 저장    ex) a가 2, 5, 8번 인덱스에 나왔다면 loc[0] = {2,5,8};

 

그리고 글자수를 돌아가며 카운트를 세고, loc에 각각 나온 인덱스를 저장해준다.

그러다가 카운트가 k개 이상이 나오면, 현재 인덱스와 loc의 마지막에서 k개만큼 빼주면, k개 이전의 인덱스가 나온다.

그럼 이제 현재 인덱스 - 이전에 같은 글자가 나왔던 인덱스 + 1을 해주면 된다. (+1을 해주는 이유는 현재인덱스와 이전인덱스를 둘다 포함해줘야 하기 때문이다.)

 

 

처음에는 vector<int> loc[30]이 아니라 int strt[30] 이라는 배열을 만들고 -1로 채운 후, 처음 해당알파벳이 나오면 해당인덱스로 채워주고, k번째 카운트 이상이 나오면 그 인덱스에서 스타트부분을 빼주고 +1 하는 식으로 하려 했었다. 

하지만 문제를 풀며 조금 생각해보니 반례가 생각났는데

ex)

1

abaa

2

일때, 

스타트만 저장하게 된다면 b다음의 a들이 스타트부분만 빼게되고, 그럼 최소값과 최대값 둘다 aba인 3만 나오게 될거라는 생각이 들었다.

그래서 vector<int>[30]으로 고쳐주고, 마지막에서 k개를 뺀 만큼 앞으로 가면, k번 전에 해당하는 인덱스가 나오고,

그걸 k번째인 현재 인덱스 - k번  전에 해당하는 인덱스 를 해주면 길이가 나올 것이라고 생각해볼 수 있었다.

 

지금 생각해보니 cnt배열도 필요 없을것 같다. 그냥 loc[s[i]].size()로 글자가 몇개 나왔나 확인할 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
int t;
string s;
int k;

int cnt[30]; // 알파벳 몇개나왔나 카운트
int main()
{
    cin >> t;
    while (t--)
    {
        int mn = 10001;
        int mx = 0;
        vector<int> loc[30]; // 어떤 글자가 나온 인덱스들을 저장    ex) a가 2, 5, 8번 인덱스에 나왔다면 loc[0] = {2,5,8};

        fill(cnt, cnt + 30, 0);
        cin >> s;
        cin >> k;
        for (int i = 0; i < s.size(); i++)
        {
            int charNum = s[i] - 'a';
            loc[charNum].push_back(i);
            cnt[charNum]++;

            if (cnt[charNum] >= k)
            {
                // int len = i - (loc[charNum].size()-k)
                int preIdx = loc[charNum].size() - k;
                int pre = loc[charNum][preIdx];
                int len = i - pre + 1;
                mn = min(mn, len);
                mx = max(mx, len);
            }
        }

        if (mn == 10001 && mx == 0)
        {
            cout << -1 << "\n";
        }
        else
        {
            cout << mn << " " << mx << "\n";
        }
    }
    return 0;
}