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

1. 코드

"""
알파벳 별 원소를 저장하는 리스트를 생각한다.
예를들어, 'a' = [1, 5, 7]라는 사전형 key-value 가 존재할 수 있다.
슬라이딩 윈도우는 [1, 5, 7]을 사이즈(k)의 윈도우를 가지고 사용한다.


input)
1
superaquatornado
2

k=2
alpha = {'u': [1, 7], 'r': [4, 11], 'a': [5, 8, 13], 'o': [10, 15]}

3번: 'a' 탐색할 때 w[5:8+1]
4번: 'r' 탐색할 때 w[4:11+1]
"""

import sys
from collections import defaultdict


t = int(sys.stdin.readline().rstrip())
for _ in range(t):
    w = sys.stdin.readline().rstrip()
    k = int(sys.stdin.readline().rstrip())

    temp_alpha = defaultdict(list)
    for i in range(len(w)):
        temp_alpha[w[i]].append(i)

    min_val = float('INF')
    max_val = -float('inf')
    alpha = defaultdict(list)
    for i in temp_alpha:
        if len(temp_alpha[i]) >= k:
            alpha[i] = temp_alpha[i][:]

    if len(alpha) == 0:
        print(-1)
        continue

    print(alpha)

    for alpha_index in alpha.values():
        for start in range(len(alpha_index)-k+1):
            temp = abs(alpha_index[start+k-1]-alpha_index[start])+1
            min_val = min(min_val, temp)
            max_val = max(max_val, temp)
    print(min_val, max_val)

---

2. 후기

처음에는 문자열 w를 대상으로 슬라이딩 윈도우를 사용하여 접근했다. 하지만 도저히 풀리지 않았다. 그래서 검색을 해봤는데 알파벳의 인덱스를 저장하고 인덱스의 리스트 안에서 슬라이딩 윈도우를 사용하는 문제였다.

고민 많이했는데 이 문제의 경우 검색을 한게 다행이라 생각한다.