백준 BOJ 16472 - 고냥이

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

16472번: 고냥이

투 포인터 알고리즘을 사용하는 골드4 문제.

 

문자열의 길이 S가 1e6으로 커서 투 포인터 알고리즘을 사용해야 한다.

구간 [s,e] 안에 있는 알파벳의 종류가 N을 넘지 않도록 관리해주면 된다.

 

알파벳의 종류를 세주기 위해서, 일반적이라면 map<char,int> 등을 만들어서 관리하게 될 텐데,

char 가 0~255 사이의 숫자 아스키코드에 대응한다는것을 통해

그냥 256개의 배열을 만드는 방법으로 map<char,int> 를 대체할 수 있다.

 

메모리를 더 아끼고 싶다면 알파벳 갯수인 26개만 만들고, arr[S[i]-'a'] 등으로 접근할 수 있겠지만,

그렇게까지 메모리를 아껴야 할 필요성이 있는 문제는 아니라서

그냥 해결했다.

 

s와 e 두개의 변수를 잡고 돌리는 투 포인터 알고리즘을 사용할 때에는

구간의 양끝을 포함시킬지, 포함시키지 않을지에 대해 헷갈리기 쉽다.

본인만의 기준을 만들어 놓던지 놓치는 부분 없도록 깔끔하게 작성하도록 하자.

필자도 이거때문에 몇번 틀렸다 ㅠㅠ

 

#include <bits/stdc++.h>
using namespace std;

int cnt[256] = {0};

int main(){
	int N;
	string S;
	
	cin >> N;
	cin >> S;
	
	int s=0;
	int e=0;
	cnt[S[0]]++;
	int now = 1;
	int ans = 1;
	
	while(e<S.length()){
		if(now <= N){
			ans = max(ans, e-s+1);
			
			e++;
			if(cnt[S[e]] == 0) now++;
			cnt[S[e]]++;
		}
		else{
			cnt[S[s]]--;
			if(cnt[S[s]] == 0) now--;
			s++;
		}
	}
	
	cout << ans;
	return 0;
}