문제 설명
고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고양이의 언어로, 고양이의 언어를 사람의 언어로 바꾸어 주는 희대의 발명품이 될 것이다.
현재 고양이말 번역기의 베타버전이 나왔다. 그러나 이 베타버전은 완전 엉망진창이다. 베타버전의 번역기는 문자열을 주면 그 중에서 최대 N개의 종류의 알파벳을 가진 연속된 문자열밖에 인식하지 못한다. 굉장히 별로지만 그나마 이게 최선이라고 사람들은 생각했다. 그리고 문자열이 주어졌을 때 이 번역기가 인식할 수 있는 최대 문자열의 길이는 얼마인지가 궁금해졌다.
고양이와 소통할 수 있도록 우리도 함께 노력해보자.
https://www.acmicpc.net/problem/16472
제한 사항
풀이
문제를 요약하면, 문자열이 주어졌을 때 N개의 문자만을 포함하는 최장 연속 부분 문자열의 길이를 구하는 것이다.
문자열의 최대 길이가 100,000개이기 때문에 문자열의 시작점을 바꿔가며 모든 문자열을 탐색하는 것은 시간 초과가 발생할 것이다.
이를 해결하기 위해서는 투포인터를 이용하면 된다.
두 포인터인 left, right가 부분 문자열의 시작과 끝이 된다.
규칙은 다음과 같다.
- left와 right 사이의 문자의 종류가 N개 이하라면 right를 계속하여 늘려나간다.
- 만약, 문자의 종류가 N개보다 커진다면 종류가 N개가 될 때까지 left를 당겨온다.
첫 번째 규칙은 단순히 right를 늘리는 과정으로 해결할 수 있다.
set과 같은 다른 자료구조를 사용하여 문자열의 종류를 확인해도 되겠지만, 문자의 종류가 26개밖에 안되기 때문에 각 문자의 포함 개수를 관리하는 배열을 통해 관리하였다.
배열을 모두 순회하여 0이 아닌 개수를 세어보면 left와 right사이에 존재하는 문자의 종류의 개수를 구할 수 있다.
vector<int> alpha(26, 0);
bool Check()
{
int cnt = 0;
for (int i = 0; i < alpha.size(); i++)
{
if (alpha[i] > 0) cnt++;
}
return cnt <= N;
}
그럼 이제 두 번째 과정만 구현하면 된다.
right와 left사이의 문자의 종류의 개수를 N개 이하로 만들기 위해서는 left가 가리키는 문자의 개수가 0이 되면 된다.
예를 들어, N=2이고 ababc라는 문자열의 각 끝을 left, right가 가리키고 있다고 가정해 보자.
right를 오른쪽으로 옮겨가다가 c를 만나는 순간 문자의 종류가 3개가 되어 N을 초과한다.
문자의 종류를 2개로 만들기 위해서는 left를 당겨오며 포함 개수가 0이 되는지 확인하면 된다.
while (--alpha[str[left++] - 'a'] > 0)
{
}
이러한 과정을 진행하며 left와 right의 차이의 최댓값을 구하면 된다.
전체 코드
#include <bits/stdc++.h>
using namespace std;
int N;
string str;
vector<int> alpha(26, 0);
bool Check()
{
int cnt = 0;
for (int i = 0; i < alpha.size(); i++)
{
if (alpha[i] > 0) cnt++;
}
return cnt <= N;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cout << fixed;
cin >> N >> str;
int left = 0;
int right = 0;
alpha[str[right] - 'a']++;
int ans = 0;
while (++right < str.length())
{
alpha[str[right] - 'a']++;
if (!Check())
{
while (--alpha[str[left++] - 'a'] > 0)
{
}
}
ans = max(ans, right - left + 1);
}
cout << ans;
return 0;
}