(Python/🥇4)백준알고리즘 16472번 : 고양이

 

문제 바로가기 

 

문제:

고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고양이의 언어로, 고양이의 언어를 사람의 언어로 바꾸어 주는 희대의 발명품이 될 것이다. 현재 고양이말 번역기의 베타버전이 나왔다. 그러나 이 베타버전은 완전 엉망진창이다. 베타버전의 번역기는 문자열을 주면 그 중에서 최대 N개의 종류의 알파벳을 가진 연속된 문자열밖에 인식하지 못한다. 굉장히 별로지만 그나마 이게 최선이라고 사람들은 생각했다. 그리고 문자열이 주어졌을 때 이 번역기가 인식할 수 있는 최대 문자열의 길이는 얼마인지가 궁금해졌다. 고양이와 소통할 수 있도록 우리도 함께 노력해보자.

입력:

첫째 줄에는 인식할 수 있는 알파벳의 종류의 최대 개수 N이 입력된다. (1 < N ≤ 26) 둘째 줄에는 문자열이 주어진다. (1 ≤ 문자열의 길이 ≤ 100,000) 단, 문자열에는 알파벳 소문자만이 포함된다.

출력:

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

 

풀이 :

 

import sys
from collections import defaultdict

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

n = int(input())
word = list(map(str,sys.stdin.readline()))
# 최대 N개의 종류의 알파벳을 가진 연속된 문자열

# two pointer
start = 0
res = 0
dic = defaultdict(int)

for right in range(len(word)):
    dic[word[right]] += 1
    while len(dic) > n:
        dic[word[start]] -= 1
        # 제거
        if dic[word[start]] == 0:
            del dic[word[start]]
        start += 1
    res = max(res, right - start + 1)
print(res)

 

투 포인터를 사용하여 풀었다.

start, right 를 0으로 설정하고

dic에다가 하나씩 추가한다.

 

dic에 길이가 n보다 작을때 까지 딕에 추가해준다.

dic은 0 이 되면 삭제되지 않으니깐 내가 del로 삭제해줘야한다.

 

매번 최댓값을 최신화한다.