[백준/C++] 16472 고냥이

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

코드

#include <iostream>
#include <unordered_map>
using namespace std;

#define FASTIO ios::sync_with_stdio(false); cin.tie(NULL);
int n, ans = 0;
string s;
unordered_map<char, int> m;

int main() {
	FASTIO;
	cin >> n >> s;

	int left=0, right = 0; 
	while (right < s.length()) {
		m[s[right]]++;

		while (m.size() > n) {
			m[s[left]]--;
			if (m[s[left]] == 0) m.erase(s[left]);
			left++;
		}
		ans = max(ans, right - left + 1);
		right++;
	}
	cout << ans << "\n";
	return 0;
}

 

설명

인식할 수 있는 알파벳의 수와 문자열을 입력받습니다.

 

while문 내에서 투포인터 알고리즘을 이용해서 문제를 풉니다. right 포인터에 위치하는 문자에 대해서 카운트를 증가시킵니다. 그리고 맵의 사이즈가 n 초과일 경우에는 left 포인터를 이동시키면서 맵에 n가지 알파벳만을 가지고 있도록 합니다. 이후 ans 값을 업데이트하고, right 포인터를 증가시켜줍니다.

 

마지막에 ans를 출력합니다.

 

느낀 점

맵을 활용한 투포인터로 문제를 풀었습니다.