[BOJ 16472] 고냥이 (Python)

문제

고냥이

---

문제 해설

투 포인터를 이용하여 문자열의 최대 길이를 구하는 문제입니다.

투 포인터를 이용해 front와 rear까지의 문자열에 대해 몇 종류의 알파벳이 들어갔는지만 확인하면 됩니다.

1. front와 rear 포인터를 만듭니다(초기 둘 다 0). 각각 찾고자하는 문자열의 처음과 끝 인덱스를 가리킵니다.
2. rear를 1씩 증가시키며 딕셔너리에 해당 알파벳과 개수를 key-value로 넣어줍니다.
3. 만약 딕셔너리의 크기가 N보다 크다면, front에 해당하는 알파벳을 딕셔너리에서 찾아 -1을 한 뒤 front를 한칸 앞으로 배치합니다. 또, 알파벳의 개수가 0이라면 딕셔너리에서 제외합니다.
4. 현재 가리키고 있는 front와 rear의 차이가 가장 긴 문자열이기 때문에 계속 갱신합니다.
5. 문자열이 끝날 때까지 반복합니다.

---

풀이 코드

import sys

input = sys.stdin.readline
n = int(input())
string = input().rstrip()
d = {}
answer = front = 0
for rear in range(len(string)):
    # rear를 1씩 증가시키며 딕셔너리의 크기를 계속 확인한다.
    d.setdefault(string[rear], 0)
    d[string[rear]] += 1
    # 만약 딕셔너리 크기가 n보다 크면 딕셔너리에서 front 값을 -1해주며 n을 맞춘다.
    while len(d) > n:
        d[string[front]] -= 1
        # 딕셔너리에서 제거
        if d[string[front]] == 0:
            del d[string[front]]
        front += 1
    answer = max(answer, rear - front + 1)
print(answer)

---