백준 16472번 고냥이 c++ 풀이

문제

고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고양이의 언어로, 고양이의 언어를 사람의 언어로 바꾸어 주는 희대의 발명품이 될 것이다.

현재 고양이말 번역기의 베타버전이 나왔다. 그러나 이 베타버전은 완전 엉망진창이다. 베타버전의 번역기는 문자열을 주면 그 중에서 최대 N개의 종류의 알파벳을 가진 연속된 문자열밖에 인식하지 못한다. 굉장히 별로지만 그나마 이게 최선이라고 사람들은 생각했다. 그리고 문자열이 주어졌을 때 이 번역기가 인식할 수 있는 최대 문자열의 길이는 얼마인지가 궁금해졌다.

고양이와 소통할 수 있도록 우리도 함께 노력해보자.

입력

첫째 줄에는 인식할 수 있는 알파벳의 종류의 최대 개수 N이 입력된다. (1 < N ≤ 26)

둘째 줄에는 문자열이 주어진다. (1 ≤ 문자열의 길이 ≤ 100,000) 단, 문자열에는 알파벳 소문자만이 포함된다.

출력

첫째 줄에 번역기가 인식할 수 있는 문자열의 최대길이를 출력한다. 

예제 입력 1 복사

2
abbcaccba

예제 출력 1 복사

4

힌트

abbcaccba에서 답은 cacc가 된다. 번역기가 인식할 수 있는 알파벳의 종류는 최대 2개이고, 알파벳의 종류를 최대 2개만 가지면서 가장 긴 연속된 문자열이 cacc이다. 따라서 답은 cacc의 길이인 4가 된다. 

 

 

투 포인터를 활용해서 풀 수 있었던 문제, 어려웠지만 끝까지 답을 안 보고 풀었다 ㅜㅜ

map을 활용하여 알파벳이 나온 횟수를 관리하고 투 포인터를 활용해서 만약에 알파벳이 나올 수 있는 한계를 넘었다면 뒤에서 부터 삭제하고 map[알파벳] -- 를 하여서 방문 관리를 하였다.

 

- c++ 풀이

#include <bits/stdc++.h>

#define visit trash
using namespace std;

int n;
string s;

map<char, int> m;

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

    cin >> n;
    cin >> s;

    int left = 0;
    int right = 0;
    string tempS = "";
    int visitCount = 0;
    int ans = 0;


    while (left <= right && right < s.length()) {

        if (visitCount <= n) {
            tempS += s[right];


            if (m[s[right]] == 0) {
                visitCount++;
            }

            if (visitCount <= n) {
                int tempSLength = tempS.length();
                ans = max(tempSLength, ans);
            }

            m[s[right]]++;
            right++;


//            cout << tempS << " / 1 " << visitCount << "\n";

        } else if (visitCount > n) {
            m[s[left]]--;
            if (m[s[left]] == 0) {
                visitCount--;
            }
            tempS.erase(0, 1);
            left++;
//            cout << tempS << " / 2 " << visitCount << "\n";

        }


    }

    cout << ans << "\n";


}