[BOJ/Python] 16472_고냥이

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

16472번: 고냥이

 

문제

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

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

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

입력

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

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

출력

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

 

예제 입력 1 

2
abbcaccba

예제 출력 1 

4

힌트

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

 

---

풀이

 

주어진 문자열에서 n종류 이하의 알파벳으로 이루어진 가장 긴 부분 문자열의 길이를 구하는 문제이다.

큐를 이용하여 문제를 해결하였고, 코드는 다음과 같다.

 

import sys
from collections import deque
 
n = int(sys.stdin.readline())
word = sys.stdin.readline().strip()
 
que = deque()
 
idx = 0
max_length = 0
count = 0
if n>=len(set(word)):
    max_length = len(word)
else:
    while idx<len(word):
 
        while count<n:
            if word[idx] not in que:
                count+=1
            que.append(word[idx])
            idx +=1
        
        if word[idx] not in que:
            length = len(que)
            max_length = max(max_length,length)
            while que:
                s = que.popleft()
                if s not in que:
                    break
        
        que.append(word[idx])
        idx+=1
 
    max_length = max(max_length,len(que))
 
print(max_length)

 

• 만약 주어진 조건 n이 문자열 속 알파벳의 종류보다 많다면, 그 문자열의 길이가 곧 최댓값이다.
• 만약 아니라면 지금부터 n종류 이하의 알파벳으로 이루어진 부분 문자열의 길이의 최댓값을 구해야 한다.
• n종류의 알파벳이 들어올 때까지, 큐에 문자열의 문자를 순차적으로 넣어준다.
• n종류의 알파벳이 들어왔다면, 지금부터는 문자열을 탐색하였을 때, 해당 문자가 현재 문자열에 존재하는지(즉, 큐 내부에 존재하는지)를 확인한다.
• 만약에 큐 내부에 없는 문자라면 이 문자까지 포함하게 되면 n+1 종류의 부분 문자열이 되므로 기존의 부분 문자열 속 문자의 종류를 n-1가지로 줄여야 한다.
• 그전에 현재 부분 문자열의 길이를 구하여 최댓값인지 확인한다.
• 이후, 먼저 들어온 문자부터 하나씩 차례로 빼내고, 빼낸 문자가 더 이상 큐 내부에 없다면 알파벳이 n-1 종류가 되므로 break를 통해 반복문을 벗어난다.
• 그러고 나서 새로운 문자를 큐에 추가한다.
• 최종적으로 문자열의 마지막까지 탐색을 하고 났을 때 만들어진 부분 문자열의 길이를 구하고, 최댓값을 구해 출력한다.