[백준/BOJ] 백준 16472번 : 고냥이

www.acmicpc.net/problem/16472

16472번: 고냥이

map<char, int> check를 통해 (문자, 개수)를 저장하여 투 포인터(두 포인터)를 이용해 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>
#include <string>
#include <queue>
#include <map>
using namespace std;

int n;
string input;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;
	cin >> input;

	int left = 0;
	int right = 0;
	map<char, int> check;
	map<char, int>::iterator it;
	int result = -1;

	while (1)
	{
		if (check.size() > n) //인식할 수 있는 알파벳 개수를 넘어갔을때
		{
			check[input[left]]--;

			if (check[input[left]] == 0)
			{
				check.erase(input[left]);
			}
			left++;
		}

		else if (right == input.size())
			break;

		else if (check.size() <= n)
		{
			it = check.find(input[right]);

			if (it == check.end()) //input[right] 알파벳이 check에 없을때
				check.insert(make_pair(input[right], 1));

			else
				(*it).second++;

			if (check.size() <= n)
				result = max(result, right - left + 1);

			right++;
		}

	}
	cout << result;

	return 0;
}