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

16472번: 고냥이

---

문제 )

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

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

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

 

입력 :

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

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

 

 

출력 :

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

 

 

풀이)

 

n = int(input())
word = input()
 
s = 0 # 투포인터
e = 0
dic = {word[e]:1} # 기본적으로 word[0]을 넣었다.
cnt = 1 # 문자열 종류의 수
answer = 0 # 최대 문자열의 길이
while e < len(word):
    if cnt <= n:
        total = 0
        for i in dic.values(): # 문자열의 개수를 total에 더함
            total += i
        if answer < total:
            answer = total # 정답 갱신
 
    if e == len(word) - 1: # 종료 조건
        break
 
    if cnt > n: # 딕셔너리를 이용한 풀이
        dic[word[s]] -= 1
        # 값이 0이 되었다면 종류의 수도 줄여야 함.
        if dic[word[s]] == 0:
            cnt -= 1
        s += 1 #포인터 전진
    else:
        e += 1
# 딕셔너리 안에 해당 값이 있다면 +1을 해주고 0에 더하는 경우 종류 +1
        if word[e] in dic:
            if dic[word[e]] == 0:
                cnt += 1
            dic[word[e]] += 1
        else:
            dic[word[e]] = 1
            cnt += 1
 
print(answer)

반례로 

5

aaaaa

를 찾는게 좀 힘들었던 문제!

---

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

16472번: 고냥이