BOJ 16472 - 고냥이

문제

백준 온라인 저지 - 16472번

풀이 과정

최대 N 개의 종류의 알파벳을 가진 연속된 문자열중에서 인식할 수 있는 최대 문자열의 길이를 구하는 문제입니다.
최대 문자열의 길이가 100,000 이기 때문에 완전 탐색 을 이용할 경우 시간 초과가 발생하게 됩니다.

대신 투 포인터 를 이용해서 N 을 초과할 경우 알파벳의 종류가 N 보다 작아질 때까지 left 를 증가시키고
N 보다 같거나 작을 경우 right 을 증가시키는 방법을 사용하면 최적화가 가능합니다.
이때 각 알파벳의 등장 횟수를 기록하기 위해 deque 를 값으로 사용하는 dict 를 사용했습니다.

각각의 deque 에는 알파벳의 인덱스가 저장되며 알파벳의 종류가 N 보다 많아졌을 시
가장 왼쪽에 있는 알파벳을 키로 하는 deque 에서 하나 dequeue 합니다.
이러한 연산을 N 보다 같거나 작아질때까지 반복하며 길이를 하나씩 줄여가며 검사하면 됩니다.
(만약 deque 가 비워질 경우 해당하는 알파벳을 dict 에서 지워줍니다.)

코드

import sys
from collections import deque

N = int(input())
S = sys.stdin.readline().strip()


def solution():
    memo = {}
    left, right = 0, 0
    answer = 1

    memo[S[right]] = deque([0])

    while left <= right:
        right += 1
        if right >= len(S):
            break

        if S[right] in memo:
            memo[S[right]].append(right)
        else:
            memo[S[right]] = deque([right])

        # 번역기 인식 범위를 넘어설 경우
        while len(memo) > N and left <= right:
            leftmost = S[left]
            memo[leftmost].popleft()
            if not memo[leftmost]:
                memo.pop(leftmost)
            left += 1

        length = right - left + 1
        answer = max(answer, length)

    return answer


print(solution())