[Two Pointers] Boj16472: 고냥이

[Two Pointers] Boj16472: 고냥이

Link: https://www.acmicpc.net/problem/16472

문제

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

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

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

입력

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

출력

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

입출력 예제

코드(시간초과)

from collections import deque
import sys
si = sys.stdin.readline
N = int(si())
word = si()
q = deque([])

def check(a):
    list_a = []
    for x in a:
        if x not in list_a:
            list_a.append(x)
        if len(list_a) > N: return False
    return len(list_a) <= N

sum = 0
ans = 0
R = 0
for L in range(len(word)):
    ans = max(ans,len(q))
    while R < len(word) and check(q)==True:
        q.append(word[R])
        R += 1
    q.popleft()

ans = max(ans,len(q))
print(ans)

시간초과가 나는 이유는 for문안에 check()함수에서 한번더 포문으로 검색하기 때문에 시간초과의 결과가 나온다.

코드(최종)

import sys
si = sys.stdin.readline

N = int(si())
word = si()[:-1]
count = [0] * 200
kind = 0

def add(x):
    global kind
    count[ord(x)] += 1
    if count[ord(x)] == 1: kind += 1

def sub(x):
    global kind
    count[ord(x)] -= 1
    if count[ord(x)] == 0: kind -= 1

L = 0
ans = 0
for R in range(len(word)):
    add(word[R])
    while kind > N:
        sub(word[L])
        L+=1
    ans = max(ans, R-L+1)

print(ans)

알파벳의 종류가 N가지 이하라면 계속해서 최대 길이를 찾을 수 있도록 하였고
N가지를 넘는다면 앞에서(왼쪽)부터 줄여나가면서 계산할 수 있도록 하였다.
종류의 계산 방법은 배열에 해당 알파벳의 크기를 늘리고 줄이면서 adding 하면서 1이되면 종류의 갯수를 늘렸고, subtracting을 하면서 0이되면 종류의 갯수를 줄였다.

코드 결과 및 스크린샷