백준 16472 - 고냥이 (파이썬)

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

풀이

1️⃣ 문제 접근

• N 개 이하의 종류의 문자로 이루어진 가장 긴 연속 부분 문자열을 찾아야 한다..
• 투 포인터 (start, end) 를 활용하여 슬라이딩 윈도우 방식으로 해결할 수 있다.

2️⃣ 알고리즘 흐름

1. 초기 세팅
   1. count 배열을 사용하여 각 문자의 개수를 저장한다.
   2. num_types를 사용하여 현재 윈도우 내 문자의 종류 개수를 저장한다.
   3. start와 end 두 개의 포인터를 활용하여 윈도우 크기를 조정한다.
2. 슬라이딩 윈도우 실행
   1. end 포인터를 확장하면서 문자 개수를 업데이트한다.
   2. num_types가 N 이하일 경우, answer 값을 갱신한다.
   3. num_types가 N을 초과하면 start 포인터를 이동하여 윈도우를 조정한다.

시간복잡도 분석

• end 포인터가 문자열 끝까지 이동하면서 O(N)
• start 포인터도 최대 N번 이동하면서 O(N)
• 전체 시간 복잡도: O(N)
• 슬라이딩 윈도우를 사용하여 한 번의 순회만으로 문제를 해결하므로 효율적

코드

# 백준 16472 - 고냥이
# 분류 : 투포인터

N = int(input())
S = input()

count = [0] * 26
num_types = 0

start = 0
end = 0
count[ord(S[0])- ord('a')] = 1
num_types = 1

answer = 0
while start < len(S) and end < len(S) :
    if num_types <= N :
        answer = max(answer, end - start + 1)
        end += 1
        if end < len(S) :
            count[ord(S[end]) - ord('a')] += 1
            if count[ord(S[end]) - ord('a')] == 1 :
                num_types += 1
    else :
        start += 1
        count[ord(S[start - 1]) - ord('a')] -= 1
        if count[ord(S[start - 1]) - ord('a')] == 0 :
            num_types -= 1

print(answer)