16472번 고냥이

제 5회 한양대학교 프로그래밍 경시대회 Open Contest - Advanced Div. E번 문제

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

2

abbcaccba

위의 예를 보자.

입력받은 문자열 인덱스 [0]부터 검사를 시작하여 다른 알파벳이 2(l)번 나올 때 까지 left와 right를 찾는다.

a b b c a c c b a

최초 left = 0, right = 2

left부터 right까지 검사하여

true의 개수가 입력한 2(l)보다 크면 ++head

작거나 같으면 ++tail

그리고, MAX = max(MAX, tail - head)를 해준다.

tail - head + 1이 아닌 이유는 74 ~ 75번 째 줄 코드에 의해 이미 head 또는 tail이 1이 증가하기 때문이다.

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
int main(void)
{
    int l = 0;
 
    bool A[27] = { false, };
 
    scanf("%d", &l);
 
    string s;
 
    cin >> s;
 
    int cnt = 0;
 
    int left = 0, right = 0, MAX = -1;
 
    bool stop = false;
 
    // 최초로 left와 right를 찾는다.
    for (int i = 0; i < s.length(); i++)
    {
        if (s.length() == 1) break;
 
        while (s[i] != s[i + 1])
        {
            ++cnt;
 
            if (cnt >= l || i + 1 == s.length())
            {
                stop = true;
                right = i;
                break;
            }
 
            ++i;
        }
 
        if (stop) break;
    }
 
    if (s.length() == 1)
    {
        printf("1\n");
        return 0;
    }
 
    while (1)
    {
        cnt = 0;
 
        memset(A, false, sizeof(A));
 
        for (int i = left; i <= right; i++)
        {
            A[s[i] - 'a'] = true;
        }
 
        for (int i = 0; i < 26; i++)
        {
            if (A[i]) ++cnt;
        }
 
        if (cnt <= l) ++right;
        else ++left;
 
        MAX = max(MAX, right - left);
 
        if (right == s.length()) break;
    }
 
    printf("%d\n", MAX);
 
    return 0;
}