[백준 16472] 고냥이 (C++)

문제 링크: www.acmicpc.net/problem/16472

16472번: 고냥이

1. 주의할 점

- 두 포인터를 이용하여 문제를 해결한다

 

2. 구현

- Alpha[] 배열을 생성하여 각 문자가 L과 R포인터 사이에 몇개 존재하는지 알려준다

- Cnt를 통해 L과 R포인터 사이에 존재하는 서로 다른 문자의 수를 표현한다

- R을 전체 문자열의 길이보다 작고, Cnt가 Num이하일때 While문을 수행하여 현재 R이 가리키는 값을 Alpha[] 배열에 표시하고, 새로운 문자라면 Cnt++한다. 이후, Cnt의 값이 Num보다 크지 않다면 Result를 R-L과 비교하여 큰 값을 저장한다

- R이 문자열의 길이와 같아졌다면 부모 While문을 종료한다

- Cnt가 Num보다 크다면 L을 오른쪽으로 한칸씩 옮기며 Alpha[]값과 Cnt값을 변경시킨다

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int alpha[26];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int num,len,result=0;
    string str;
    cin>>num>>str;
    len = str.size();
    int l=0,r=0,cnt=0;
    while(1){
        while(cnt<=num && r<len){
            int idx = str[r++]-'a';
            alpha[idx]++;
            if(alpha[idx]==1) cnt++;
            if(cnt>num) break;
            result = max(result,r-l);
        }
        if(r==len) break;
        while(cnt>num){
            int val = str[l]-'a';
            l++;
            alpha[val]--;
            if(alpha[val]==0) cnt--;
        }
    }
    cout<<result;
    return 0;
}