문제 이해 단계
https://www.acmicpc.net/problem/16472
16472번: 고냥이
고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고
www.acmicpc.net
소문자로 이루어진 알파벳 문자열이 주어진다.
또한 입력으로 N이 주어지는데, 서로 다른 종류의 알파벳을 인식할 수 있는 개수이다.
구해야 하는 것은 N개의 서로 다른 종류의 알파벳을 인식할 수 있을 때,
주어진 문자열에서 인식할 수 있는 연속된 문자열 중 최대 길이를 구하는 문제
문제 접근 단계
늘 그렇듯, 제한사항부터 알아보자.입력 N은 최대 26까지,
문자열의 길이는 최대 100,000까지 가능하다.
이중 반복으로 100,000 * 26을 모두 살펴보아도 시간초과가 나지는 않는다.
해당 문자열의 최대 길이를 구한다고 했을 때,
N개의 서로 다른 종류의 알파벳을
1.. 2.. K.. N-1.. N
이렇게 1부터 올려보자.
N = 1 일 때, 인덱스 0부터 탐색해 보자.
N = 1 일 때, 인덱스 0부터 나올 수 있는 일부분을 그려봤다.
보다시피 길이가 2일 때가 최대이다.
N = 2 일 때를 보면
이렇게 cacc가 최대길이 4가 된다.
그런데 여기서 그치지 않고 N = 3 이 된다고 생각해 보자.
이렇게 될 것이다.
문자열의 최댓값을 구할 때 왼쪽에서 오른쪽으로만 무조건 이동한다.
이 점을 보았을 때, 이는 왼쪽에서 오른쪽을 탐색하면서
중복을 확인하는 방법을 사용하면 될 것 같다.
이때 생각난 것이 투포인터였다.
정답 문자열의 시작점과 마지막점을 두 개의 포인터로 잡는다.
시작점을 옮겨가며, 다른 알파벳을 인식할 수 있는 기회 N을 가진 채로 끝 포인트를 옮겨간다.
이미 인식할 수 있는 알파벳이면 인식 기회 N을 유지한 채 끝 포인트를 옮긴다.
새로운 알파벳이면 인식 기회를 N-1 하고 끝 포인트를 옮긴다.
해당 과정을 반복하다가 N이 0이 되면 반복을 종료하고,
시작위치와 끝위치 사이 길이를 구한다.
이 과정을 모든 문자에 위치를 시작점으로 하여 실행하여 최댓값을 구한다.
자세한 것은 코드를 통해 설명하겠다.
문제 구현 단계
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int N;
cin >> N;
string str;
cin >> str;
int ans = 0;
// 시작 위치를 인덱스 0부터 끝까지 하나씩 올림
for(int i = 0; i < str.length(); i++){
int word[28]; // 해당 알파벳의 개수
memset(word,0,sizeof(word)); // 시작 위치를 옮길때마다 초기화
int right = i; // 끝 위치(right)를 왼쪽 위치와 동일하게 초기화
int cnt = 0; // 현재 인식한 다른 알파벳의 개수
// 끝 위치가 문자열의 길이를 넘거나, 인식할 수 있는 알파벳의 갯수를 넘었을 때
while(right < str.length() && cnt <= N){
int num = str[right]-'a'; // 개수를 위해 'a'를 뻬줌
word[num]++;
if(word[num] == 1) cnt++; // 새롭게 생긴 알파벳이란 뜻
if(cnt > N) break;
ans = max(ans,right-i+1); // 개수
right++; // 끝 위치를 옮김
}
if(right == str.length()) break; // 끝 위치가 마지막까지 온 것이라면 종료
}
cout << ans;
}투포인터를 구현한 함수이다.
이중반복문의 바깥은 시작위치를 나타내는데, 0부터 문자열의 마지막 인덱스까지 간다.
word 배열은 안에 알파벳의 개수를 저장한다.
시작위치를 바꿀 때마다 초기화해줘야 한다.
내부에 있는 반복문은 끝 위치를 바꾸는 것인데, 매번 +1씩 뒤로 옮겨준다.
이때 새로 생긴 알파벳인지 아닌지에 따라 cnt를 더해주는지 말지 결정해 준다.
이후 반환할 때는 끝위치 - 시작위치 +1을 해줘 길이를 반환한다.
여기서 if(right == str.length()) break;
으로 끝위치가 문자열의 끝에 다다랐을 때 아예 종료한다.
그 이유는 해당 상태가 됐다는 것은 cnt <= N인 상태에서 온 것이기에,
더 이상 볼 필요도 없이 여태까지 했던 것에 최소이기 때문이다.
여기까지가 설명의 끝이다.
시행착오
처음에는 DP인 줄 알았다.
확신했다. 근데 아무리 풀어봐도 안되더라. 실패했다.
이거 두포인터라던데 와.. 보니까 당연히 투포인터더라.
화나서 시간복잡도 찾아보니까
O(N).. 투포인터가 좋긴 좋네..근데 생각보다 구현이 어려웠다..
투 포인터도 많이 풀어보긴 해야지..
생각보다 많이 쓰이네
생활비..