[BOJ/백준][Gold4] 16472 : 고냥이 (C++)

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

16472번: 고냥이

 

 

[난이도] Gold4
[유형] 투포인터

[풀이]
입력문자열의 앞부터 확인하면서 a[26] 배열에 각 문자를 몇개 사용했는지를 기록해줍니다.
그러다 N개의 문자를 넘게 사용하게 되면 현재 체크중인 문자열의 맨 앞 index부터 문자열에서
제거해주면서 a[26] 배열을 업데이트 해줍니다. a[k] > 0 이었다가 a[k] == 0 인 문자가 나타나면
이제 맨 뒤 쪽에 이어서 문자를 추가해줄 수 있기 때문에 뒤쪽에 다시 문자들을 붙혀줍니다.

 

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int N,a[26],ans,v,start;
string s;
int main(){
    cin >> N >> s;
    string cur;
    for(int i=0;i<s.size();i++){
        int cnt=0;
        for(int j=0;j<26;j++) {
            if(a[j]>0) cnt++;
        }
        if(cnt<N || a[s[i]-'a']){
            v++;
            a[s[i]-'a']++;
            ans=max(ans,v);
            continue;
        }
        for(int j=start;j<=i;j++){
            v--;
            if(--a[s[j]-'a'] == 0){
                start=j+1;
                break;
            }
        }
        i--;
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/16472.cpp