[백준] 16472번: 고냥이 (C++)

 

16472번: 고냥이

---

문제 )

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

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

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

 

 

 

입력 :

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

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

 

 

출력 :

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

 

 

 

 

 

풀이)

처음으로 cpp에서 python의 딕셔너리와 유사한 map을 써보았다.

 

생각보다 사용하는 방법이 달라 조금 헤메긴 했지만, 

 

곧 금방 적응할 수 있었다.

 

까먹지 않게 블로그에 잘 적어 체득할 수 있도록 해야겠다.

 

기본적인 문제의 풀이는 투포인터를 활용하며, 앞에 있는 포인터인 s가 이동할 때, 

 

가지고 있는 문자의 개수를 체크하고, 투 포인터 사이에 있는 문자열의 길이를 체크해 

 

최대길이를 답으로 내면 된다.

 

 

#include <iostream>
#include <map>
#include <string>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    cin.ignore();
 
    string word;
    cin >> word;
 
    int s = 0;
    int e = 0;
    map<char, int> m;
    m[word[0]] = 1;
 
    int answer = 0;
    int cnt = 1;
    while(e < word.size()){
        if(cnt <= n) {
            int total = 0;
            for(auto j = m.begin(); j != m.end(); j++) {
                total += j->second;
            }
            if(answer < total) {
                answer = total;
            }
        }
 
        if(e == word.size() - 1) break;
 
        if(cnt > n) {
            m[word[s]] -= 1;
            if(m[word[s]] == 0) {
                cnt--;
            }
            s++;
        } else {
            e++;
            if(m.find(word[e]) != m.end()) {
                if(m[word[e]] == 0) {
                    cnt++;
                }
                m[word[e]]++;
            } else {
                m[word[e]] = 1;
                cnt++;
            }
        }
    }
 
    cout << answer;
 
 
    return 0;
 
}

 

---

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

16472번: 고냥이