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

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

16472번: 고냥이

 

 

[ 문제풀이 ]

 

1. N과 문자열을 입력받고, 문자의 개수를 저장할 cnt 배열과 총 문자 종류의 개수를 저장할 ch배열을 초기화합니다.

 

2. s = 0, e = 0으로 초기화한 후 e < str.size()인 동안 반복하면서 총 문자 종류의 개수가 N개보다 적거나 같으면 ans에 문자열의 길이의 최댓값을 저장하고, e++, cnt++, 처음 나오는 문자라면 ch++를 해주고, N개보다 많다면 cnt--, s++, 해당 문자의 개수가 0개라면 ch--를 해줍니다.

 

3. ans를 출력합니다.

 

[ 소스코드 ]

#include<iostream>
#include<string>
 
using namespace std;
 
int N;
string str;
int cnt[26];
int ch;
int ans;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    cin >> str;
 
    int s = 0;
    int e = 0;
 
    cnt[str[0] - 'a']++;
    ch++;
    ans = 1;
 
    while (e < str.size()) {
        if (ch <= N) {
            ans = max(ans, e - s + 1);
            e++;
            if (cnt[str[e] - 'a'] == 0) ch++;
            cnt[str[e] - 'a']++;
        }
        else {
            cnt[str[s] - 'a']--;
            if (cnt[str[s] - 'a'] == 0) ch--;
            s++;
        }
    }
 
    cout << ans;
}